Article

Separating agreement from execution for byzantine fault tolerant services

Authors:

Jean-Philippe Martin,

Arun Venkataramani,

Lorenzo Alvisi,

Mike DahlinAuthors Info & Claims

SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principles

Pages 253 - 267

https://doi.org/10.1145/945445.945470

Published: 19 October 2003 Publication History

Abstract

We describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement that orders requests from execution that processes requests. This separation yields two fundamental and practically significant advantages over previous architectures. First, it reduces replication costs because the new architecture can tolerate faults in up to half of the state machine replicas that execute requests. Previous systems can tolerate faults in at most a third of the combined agreement/state machine replicas. Second, separating agreement from execution allows a general privacy firewall architecture to protect confidentiality through replication. In contrast, replication in previous systems hurts confidentiality because exploiting the weakest replica can be sufficient to compromise the system. We have constructed a prototype and evaluated it running both microbenchmarks and an NFS server. Overall, we find that the architecture adds modest latencies to unreplicated systems and that its performance is competitive with existing Byzantine fault tolerant systems.

References

[1]

A. Adya, W. Bolosky, M. Castro, G. Cermak, R. Chaiken, J. Douceur, J. Howell, J. Lorch, M. Theimer, and R. Wattenhofer. FARSITE: Federated available and reliable storage for incompletely trusted environments. In 5th Symp on Operating Systems Design and Impl., December 2002.]]

Digital Library

[2]

P. Ammann and J. Knight. Data diversity: An approach to software fault tolerance. IEEE Trans. Comput., 37(4):418--425, 1988.]]

Digital Library

[3]

M. Baker. Fast Crash Recovery in Distributed File Systems. PhD thesis, University of California at Berkeley, 1994.]]

Digital Library

[4]

R. Baldoni, C. Marchetti, and S. Piergiovanni. Asynchronous active replication in three-tier distributed systems, 2002.]]

Digital Library

[5]

M. Bellare and D. Micciancio. A new paradigm for collision-free hashing: Incrementally at reduced cost. In Eurocrypt97, 1997.]]

Digital Library

[6]

A. D. Birrell, A. Hisgen, C. Jerian, T. Mann, and G. Swart. The Echo distributed file system. Technical Report 111, Palo Alto, CA, USA, 10 1993.]]

[7]

G. Bracha and S. Toueg. Asynchronous consensus and broadcast protocols. J. of the ACM, 32(4):824--840, October 1985.]]

Digital Library

[8]

M. Burrows, M. Abadi, and R. Needham. A Logic of Authentication. In ACM Trans. on Computer Systems, pages 18--36, February 1990.]]

Digital Library

[9]

R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute of Science, 1995.]]

[10]

R. Canetti and T. Rabin. Optimal Asynchronous Byzantine Agreement. Technical Report 92-15, Dept. of Computer Science, Hebrew University, 1992.]]

[11]

M. Castro and B. Liskov. Practical byzantine fault tolerance. In 3rd Symp. on Operating Systems Design and Impl., February 1999.]]

Digital Library

[12]

M. Castro and B. Liskov. Proactive recovery in a Byzantine-Fault-Tolerant system. In 4th Symp. on Operating Systems Design and Impl., pages 273--288, 2000.]]

Digital Library

[13]

D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. In Comm. of the ACM, volume~24, pages 84--90, February 1981.]]

Digital Library

[14]

P. Chen, W. Ng, S. Chandra, C. Aycock, G. Rajamani, and D. Lowell. The Rio File Cache: Surviving Operating System Crashes. In 7th Internat. Conf. on Arch. Support for Programming Languages and Operating Systems, October 1996.]]

Digital Library

[15]

F. Cristian and C. Fetzer. The timed asynchronous distributed system model. IEEE Transactions on Parallel and Distributed Systems, 10(6):642--657, 1999.]]

Digital Library

[16]

Y. Desmedt and Y. Frankel. Threshold cryptosystems. In Advances in Cryptology: Crypto'89, the Ninth Annual International Cryptology Conference, pages 307--315, 1990.]]

Digital Library

[17]

S. Even, O. Goldreich, and A. Lempel. A Randomized Protocol for Signing Contracts. Comm. of the ACM, 28:637--647, 1985.]]

Digital Library

[18]

M. Fischer, N. Lynch, and M. Paterson. Impossibility of distributed commit with one faulty process. J. of the ACM, 32(2), April 1985.]]

Digital Library

[19]

J. Garay, R. Gennaro, C. Jutla, and T. Rabin. Secure distributed storage and retrieval. Theoretical Computer Science, 243(1-2):363--389, July 2000.]]

Digital Library

[20]

J. Garay and Y. Moses. Fully Polynomial Byzantine Agreement for n>3t Processors in t+1 Rounds. SIAM Journal of Compouting, 27(1), 1998.]]

Digital Library

[21]

J. Howard, M. Kazar, S. Menees, D. Nichols, M. Satyanarayanan, R. Sidebotham, and M. West. Scale and Performance in a Distributed File System. ACM Trans. on Computer Systems, 6(1):51--81, February 1988.]]

Digital Library

[22]

A. Iyengar, R. Cahn, C. Jutla, and J. Garay. Design and Implementation of a Secure Distributed Data Repository. In Proc. of the 14th IFIP Internat. Information Security Conf., pages 123--135, 1998.]]

[23]

R. Karp, M. Luby, and F. auf~der Heide. Proactive Secret Sharing or How to Cope with Perpetual Leakage. In Proc. of the 15th Annual Internat. Cryptology Conf., pages 457--469, 1995.]]

Digital Library

[24]

K. Kihlstrom, L. Moser, and P. Melliar-Smith. The securering protocols for securing group communication. In Hawaii International Conference on System Sciences, 1998.]]

Digital Library

[25]

J. Knight and N. Leveson. An experimental evaluation of the assumption of independence in multi-version programming. IEEE Trans. Softw. Eng., 12(1):96--109, 1986.]]

Digital Library

[26]

J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. OceanStore: An Architecture for Global-Scale Persistent Storage. In 9th Internat. Conf. on Arch. Support for Programming Languages and Operating Systems, November 2000.]]

Digital Library

[27]

S. Kumar and K. Li. Using model checking to debug device firmware. In 5th Symp on Operating Systems Design and Impl., 2002.]]

Digital Library

[28]

L. Lamport. Time, clocks, and the ordering of events in a distributed system. Comm. of the ACM, 21(7), July 1978.]]

Digital Library

[29]

L. Lamport. Part time parliament. ACM Trans. on Computer Systems, 16(2), May 1998.]]

Digital Library

[30]

L. Lamport. Paxos made simple. ACM SIGACT News Distributed Computing Column, 32(4), December 2001.]]

[31]

L. Lamport, R. Shostack, and M. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3):382--401, 1982.]]

Digital Library

[32]

B. Liskov, S. Ghemawat, R. Gruber, P. Johnson, L. Shrira, and M. Williams. Replication in the Harp File System. In 13th ACM Symposium on Operating Systems Principles, October 1991.]]

Digital Library

[33]

D. Malkhi and M. Reiter. Byzantine quorum systems. Distributed Computing, pages 203--213, 1998.]]

Digital Library

[34]

D. Mazieres, M. Kaminsky, M. F. Kaashoek, and E. Witchel. Separating key management from file system security. In 17th ACM Symposium on Operating Systems Principles, December 1999.]]

Digital Library

[35]

J. McLean. A general theory of composition for a class of 'possibilistic' security properties. IEEE Trans. on Software Engineering, 22(1):53--67, January 1996.]]

Digital Library

[36]

M. Musuvathi, D. Park, A. Chou, D. Engler, and D. Dill. CMC: A pragmatic approach to model checking real code. In 5th Symp on Operating Systems Design and Impl., 2002.]]

Digital Library

[37]

J-F. Paris and D. D. E. Long. Voting with regenerable volatile witnesses. In ICDE, pages 112--119, 1991.]]

Digital Library

[38]

M. Reiter. The Rampart toolkit for building high-integrity services. In Dagstuhl Seminar on Dist. Sys., pages 99--110, 1994.]]

Digital Library

[39]

R. L. Rivest, A. Shamir, and L. M. Adelman. A method for obtaining digital signatures and pulic-key cryptosystems. Comm. of the ACM, 21(2):120--126, 1978.]]

Digital Library

[40]

R. Rodrigues, M. Castro, and B. Liskov. Base: Using abstraction to improve fault tolerance. In 18th ACM Symposium on Operating Systems Principles, October 2001.]]

Digital Library

[41]

A. Rowstron and P. Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In 18th ACM Symposium on Operating Systems Principles, 2001.]]

Digital Library

[42]

A. Sabelfeld and A. Myers. Language-based information-flow security, 2003.]]

[43]

F. Schneider. Implementing Fault-tolerant Services Using the State Machine Approach: A tutorial. Computing Surveys, 22(3):299--319, September 1990.]]

Digital Library

[44]

Secure hash standard. Federal Information Processing Standards Publication (FIPS) 180-1, April 1995.]]

[45]

M. Shand and J. E. Vuillemin. Fast implementations of RSA cryptography. In E. E. Swartzlander, M. J. Irwin, and J. Jullien, editors, Proceedings of the 11th IEEE Symposium on Computer Arithmetic, pages 252--259, Windsor, Canada, 1993. IEEE Computer Society Press, Los Alamitos, CA.]]

[46]

Q. Sun, D. Simon, Y. Wang, W. Russell, V. Padmanabhan, and L. Qiu. Statistical identification of encrypted web browsing traffic. In Proc. of IEEE Symposium on Security and Privacy, May 2002.]]

Digital Library

[47]

G. Tsudik. Message authentication with one-way hash functions. ACM Computer Comm. Review, 22(5), 1992.]]

Digital Library

[48]

U. Voges and L. Gmeiner. Software diversity in reacter protection systems: An experiment. In IFAC Workshop SAFECOMP79, May 1979.]]

[49]

M. Welsh, D. Culler, and E. Brewer. SEDA: An architecture for well-conditioned, scalable internet services. In 18th ACM Symposium on Operating Systems Principles, pages 230--243, 2001.]]

Digital Library

[50]

J. Yin, J-P. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin. Byzantine fault-tolerant confidentiality. In Proceedings of the International Workshop on Future Directions in Distributed Computing, pages 12--15, June 2002.]]

[51]

J. Yin, J-P. Martin, A. Venkataramani, M. Dahlin, and L. Alvisi. Separating agreement from execution for byzantine fault tolerant services. Technical report, University of Texas at Austin, Department of Computer Sciences, August 2003.]]

[52]

L. Zhou, F. Schneider, and R. van Renesse. COCA : A Secure Distributed On-line Certification Authority. ACM Trans. on Computer Systems, 20(4):329--368, November 2002.]]

Digital Library

Cited By

Jamshidi KVora KLee IChabbi MSteuwer M(2024)OsirisBFT: Say No to Task Replication for Scalable Byzantine Fault Tolerant AnalyticsProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638468(94-108)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638468
Ye ZMisra UCheng JZhou WSong D(2024)Specular: Towards Secure, Trust-minimized Optimistic Blockchain Execution2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00175(3943-3960)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00175
Xu YXu GLiu YLiu YShen M(2024)A survey of the fusion of traditional data security technology and blockchainExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.124151252:PAOnline publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.124151
Show More Cited By

Index Terms

Separating agreement from execution for byzantine fault tolerant services
1. Security and privacy
  1. Systems security
    1. Information flow control
    2. Operating systems security
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Practical byzantine fault tolerance and proactive recovery

Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions ...
Separating agreement from execution for byzantine fault tolerant services
SOSP '03

We describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement that orders requests from execution that processes requests. This separation yields two fundamental and practically significant advantages ...
Deterministic or probabilistic? - A survey on Byzantine fault tolerant state machine replication
Highlights
- Network infrastructures and software systems are vulnerable to failures.
- Service replication is a solution that guarantees the service’s correct execution even in the presence of faults.
- The use of a consensus protocol is necessary ...
Abstract
Byzantine Fault tolerant (BFT) protocols are implemented to guarantee the correct system/application behavior even in the presence of arbitrary faults (i.e., Byzantine faults). Byzantine Fault tolerant State Machine Replication (BFT-SMR) is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principles

October 2003

338 pages

ISBN:1581137575

DOI:10.1145/945445

General Chair:
Michael L. Scott
University of Rochester
,
Program Chair:
Larry Peterson
Princeton University

ACM SIGOPS Operating Systems Review Volume 37, Issue 5
SOSP '03
December 2003
329 pages
ISSN:0163-5980
DOI:10.1145/1165389
Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SOSP03

Sponsor:

SOSP03: ACM Symposium on Operating Systems Principles

October 19 - 22, 2003

NY, Bolton Landing, USA

Acceptance Rates

SOSP '03 Paper Acceptance Rate 22 of 128 submissions, 17%;

Overall Acceptance Rate 131 of 716 submissions, 18%

Upcoming Conference

SOSP '24

Sponsor:
sigops

ACM SIGOPS 30th Symposium on Operating Systems Principles

November 4 - 6, 2024

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

191
Total Citations
View Citations
1,536
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)4

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jamshidi KVora KLee IChabbi MSteuwer M(2024)OsirisBFT: Say No to Task Replication for Scalable Byzantine Fault Tolerant AnalyticsProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638468(94-108)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638468
Ye ZMisra UCheng JZhou WSong D(2024)Specular: Towards Secure, Trust-minimized Optimistic Blockchain Execution2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00175(3943-3960)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00175
Xu YXu GLiu YLiu YShen M(2024)A survey of the fusion of traditional data security technology and blockchainExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.124151252:PAOnline publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.124151
Mane SLyu FReed BGonzalez Boix ESutra P(2023)Verify, And Then Trust: Data Inconsistency Detection in ZooKeeperProceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3578358.3591328(16-22)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3578358.3591328
Aguilera MBen-David NGuerraoui RMurat AXygkis AZablotchi IAamodt TJerger NSwift M(2023)uBFT: Microsecond-Scale BFT using Disaggregated MemoryProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575732(862-877)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575732
Khan MBabay A(2023)Making Intrusion Tolerance Accessible: A Cloud-Based Hybrid Management Approach to Deploying Resilient Systems2023 42nd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS60354.2023.00033(254-267)Online publication date: 25-Sep-2023
https://doi.org/10.1109/SRDS60354.2023.00033
Graf MKüsters RRausch D(2023)AUC: Accountable Universal Composability2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179384(1148-1167)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179384
Distler TEischer MLawniczak L(2023)Micro Replication2023 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58367.2023.00024(123-137)Online publication date: Jun-2023
https://doi.org/10.1109/DSN58367.2023.00024
Wang GNixon M(2023)SoK: Essentials of BFT Consensus for Blockchains2023 Fifth International Conference on Blockchain Computing and Applications (BCCA)10.1109/BCCA58897.2023.10338868(315-328)Online publication date: 24-Oct-2023
https://doi.org/10.1109/BCCA58897.2023.10338868
Suri-Payer FBurke MWang ZZhang YAlvisi LCrooks N(2021)BasilProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483552(1-17)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483552
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents