Separating agreement from execution for byzantine fault tolerant services

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: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 2: Paul E. Ammann , John C. Knight, Data Diversity: An Approach to Software Fault Tolerance, IEEE Transactions on Computers, v.37 n.4, p.418-425, April 1988 [doi>10.1109/12.2185]
• 3: Mary Louise Gray Baker, Fast crash recovery in distributed file systems, University of California at Berkeley, Berkeley, CA, 1995
• 4: Roberto Baldoni , Carlo Marchetti , Sara Tucci Piergiovanni, Asynchronous Active Replication in Three-Tier Distributed Systems, Proceedings of the 2002 Pacific Rim International Symposium on Dependable Computing, p.19, December 16-18, 2002
• 5: M. Bellare and D. Micciancio. A new paradigm for collision-free hashing: Incrementally at reduced cost. In Eurocrypt97, 1997.
• 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: Gabriel Bracha , Sam Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM (JACM), v.32 n.4, p.824-840, Oct. 1985 [doi>10.1145/4221.214134]
• 8: Michael Burrows , Martin Abadi , Roger Needham, A logic of authentication, ACM Transactions on Computer Systems (TOCS), v.8 n.1, p.18-36, Feb. 1990 [doi>10.1145/77648.77649]
• 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: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 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.
• 13: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 14: Peter M. Chen , Wee Teck Ng , Subhachandra Chandra , Christopher Aycock , Gurushankar Rajamani , David Lowell, The Rio file cache: surviving operating system crashes, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.74-83, October 01-04, 1996, Cambridge, Massachusetts, United States
• 15: Flaviu Cristian , Christof Fetzer, The Timed Asynchronous Distributed System Model, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.642-657, June 1999 [doi>10.1109/71.774912]
• 16: Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
• 17: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 18: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 19: Juan A. Garay , Rosario Gennaro , Charanjit Jutla , Tal Rabin, Secure distributed storage and retrieval, Theoretical Computer Science, v.243 n.1-2, p.363-389, July 28, 2000 [doi>10.1016/S0304-3975(98)00263-1]
• 20: Juan A. Garay , Yoram Moses, Fully Polynomial Byzantine Agreement for Processors in Rounds, SIAM Journal on Computing, v.27 n.1, p.247-290, Feb. 1998 [doi>10.1137/S0097539794265232]
• 21: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 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: Amir Herzberg , Stanislaw Jarecki , Hugo Krawczyk , Moti Yung, Proactive Secret Sharing Or: How to Cope With Perpetual Leakage, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.339-352, August 27-31, 1995
• 24: Kim Potter Kihlstrom , L. E. Moser , P. M. Melliar-Smith, The SecureRing Protocols for Securing Group Communication, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 3, p.317, January 06-09, 1998 [doi>10.1109/HICSS.1998.656294]
• 25: J. C. Knight , N. G. Leveson, An experimental evaluation of the assumption of independence in multiversion programming, IEEE Transactions on Software Engineering, v.12 n.1, p.96-109, Jan. 1986
• 26: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 27: Sanjeev Kumar , Kai Li, Using model checking to debug device firmware, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060296]
• 28: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 29: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 30: L. Lamport. Paxos made simple. ACM SIGACT News Distributed Computing Column, 32(4), December 2001.
• 31: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 32: Barbara Liskov , Sanjay Ghemawat , Robert Gruber , Paul Johnson , Liuba Shrira, Replication in the harp file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.226-238, October 13-16, 1991, Pacific Grove, California, United States
• 33: Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Distributed Computing, v.11 n.4, p.203-213, October 1998 [doi>10.1007/s004460050050]
• 34: David Mazières , Michael Kaminsky , M. Frans Kaashoek , Emmett Witchel, Separating key management from file system security, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.124-139, December 12-15, 1999, Charleston, South Carolina, United States
• 35: John McLean, A General Theory of Composition for a Class of "Possibilistic" Properties, IEEE Transactions on Software Engineering, v.22 n.1, p.53-67, January 1996 [doi>10.1109/32.481534]
• 36: Madanlal Musuvathi , David Y. W. Park , Andy Chou , Dawson R. Engler , David L. Dill, CMC: a pragmatic approach to model checking real code, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060297]
• 37: Jehan-François Pâris , Darrell D. E. Long, Voting with Regenerable Volatile Witnesses, Proceedings of the Seventh International Conference on Data Engineering, p.112-119, April 08-12, 1991
• 38: Michael K. Reiter, The Rampart Toolkit for Building High-Integrity Services, Selected Papers from the International Workshop on Theory and Practice in Distributed Systems, p.99-110, September 05-09, 1994
• 39: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 40: Rodrigo Rodrigues , Miguel Castro , Barbara Liskov, BASE: using abstraction to improve fault tolerance, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 41: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 42: A. Sabelfeld and A. Myers. Language-based information-flow security, 2003.
• 43: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 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: Qixiang Sun , Daniel R. Simon , Yi-Min Wang , Wilf Russell , Venkata N. Padmanabhan , Lili Qiu, Statistical Identification of Encrypted Web Browsing Traffic, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.19, May 12-15, 2002
• 47: Gene Tsudik, Message authentication with one-way hash functions, ACM SIGCOMM Computer Communication Review, v.22 n.5, p.29-38, Oct. 1992 [doi>10.1145/141809.141812]
• 48: U. Voges and L. Gmeiner. Software diversity in reacter protection systems: An experiment. In IFAC Workshop SAFECOMP79, May 1979.
• 49: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 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: Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, COCA: A secure distributed online certification authority, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.329-368, November 2002 [doi>10.1145/571637.571638]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Information flow controls

General Terms:
Performance, Reliability, Security

Keywords:
byzantine fault tolerance, confidentialiy, reliability, security, state machine replication, trustworthy systems