Fault-scalable Byzantine fault-tolerant services

ABSTRACT

A fault-scalable service can be configured to tolerate increasing numbers of faults without significant decreases in performance. The Query/Update (Q/U) protocol is a new tool that enables construction of fault-scalable Byzantine fault-tolerant services. The optimistic quorum-based nature of the Q/U protocol allows it to provide better throughput and fault-scalability than replicated state machines using agreement-based protocols. A prototype service built using the Q/U protocol outperforms the same service built using a popular replicated state machine implementation at all system sizes in experiments that permit an optimistic execution. Moreover, the performance of the Q/U protocol decreases by only 36% as the number of Byzantine faults tolerated increases from one to five, whereas the performance of the replicated state machine decreases by 83%.

REFERENCES

• 1: Michael Abd-El-Malek , Gregory R. Ganger , Michael K. Reiter , Jay J. Wylie , Garth R. Goodson, Lazy Verification in Fault-Tolerant Distributed Storage Systems, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems (SRDS'05), p.179-190, October 26-28, 2005 [doi>10.1109/RELDIS.2005.20]
• 2: M. Abd-El-Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie. The Read/Conditional-Write and Query/Update protocols. Technical report CMU--PDL--05--107. Parallel Data Laboratory, Carnegie Mellon University, Pittsburgh, PA, August 2005.
• 3: 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]
• 4: Marcos Kawazoe Aguilera , Wei Chen , Sam Toueg, Failure detection and consensus in the crash-recovery model, Distributed Computing, v.13 n.2, p.99-125, April 2000 [doi>10.1007/s004460050070]
• 5: Mihir Bellare , Ran Canetti , Hugo Krawczyk, Keying Hash Functions for Message Authentication, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.1-15, August 18-22, 1996
• 6: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 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: Christian Cachin , Jonathan A. Poritz, Secure Intrusion-tolerant Replication on the Internet, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.167-176, June 23-26, 2002
• 9: Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002 [doi>10.1145/571637.571640]
• 10: Backoff Protocols for Distributed Mutual Exclusion and Ordering, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.11, April 16-19, 2001
• 11: Charles P. Fry , Michael K. Reiter, Nested Objects in a Byzantine Quorum-Replicated System, Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems (SRDS'04), p.79-89, October 18-20, 2004
• 12: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 13: S. D. Gribble, E. A. Brewer, J. M. Hellerstein, and D. Culler. Scalable, distributed data structures for internet service construction. Symposium on Operating Systems Design and Implementation, 2000.
• 14: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 15: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 16: Ricardo Jiménez-Peris , M. Patiño-Martínez , Gustavo Alonso , Bettina Kemme, Are quorums an alternative for data replication?, ACM Transactions on Database Systems (TODS), v.28 n.3, p.257-294, September 2003 [doi>10.1145/937598.937601]
• 17: J. Katcher. PostMark: a new file system benchmark. Technical report TR3022. Network Appliance, October 1997.
• 18: Kim Potter Kihlstrom , L. E. Moser , P. M. Melliar-Smith, The SecureRing group communication system, ACM Transactions on Information and System Security (TISSEC), v.4 n.4, p.371-406, November 2001 [doi>10.1145/503339.503341]
• 19: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 20: Klaus Kursawe, Optimistic Byzantine Agreement, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.262, October 13-16, 2002
• 21: 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]
• 22: 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]
• 23: L. L. Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks, 2:95--114, 1978.
• 24: Witold Litwin , Thomas Schwarz, LH*RS: a high-availability scalable distributed data structure using Reed Solomon Codes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.237-248, May 15-18, 2000, Dallas, Texas, United States
• 25: J. MacCormick, N. Murphy, M. Najork, C. A. Thekkath, and L. Zhou. Boxwood: abstractions as the foundation for storage infrastructure. Symposium on Operating Systems Design and Implementation, pages 105--120. USENIX Association, 2004.
• 26: Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Distributed Computing, v.11 n.4, p.203-213, October 1998 [doi>10.1007/s004460050050]
• 27: Dahlia Malkhi , Michael K. Reiter , Avishai Wool, The Load and Availability of Byzantine Quorum Systems, SIAM Journal on Computing, v.29 n.6, p.1889-1906, April 2000 [doi>10.1137/S0097539797325235]
• 28: Dahlia Malkhi , Michael K. Reiter, An Architecture for Survivable Coordination in Large Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.187-202, March 2000 [doi>10.1109/69.842262]
• 29: Jean-Philippe Martin, Fast Byzantine Consensus, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.402-411, June 28-July 01, 2005 [doi>10.1109/DSN.2005.48]
• 30: Jean-Philippe Martin , Lorenzo Alvisi , Michael Dahlin, Minimal Byzantine Storage, Proceedings of the 16th International Conference on Distributed Computing, p.311-325, October 28-30, 2002
• 31: R. Morris. Storage: from atoms to people. Keynote address at Conference on File and Storage Technologies, January 2002.
• 32: Moni Naor , Avishai Wool, The Load, Capacity, and Availability of Quorum Systems, SIAM Journal on Computing, v.27 n.2, p.423-447, April 1998 [doi>10.1137/S0097539795281232]
• 33: 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
• 34: Sean Rhea , Patrick Eaton , Dennis Geels , Hakim Weatherspoon , Ben Zhao , John Kubiatowicz, Awarded Best Student Paper! - Pond: The OceanStore Prototype, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 35: R. L. Rivest. The MD5 message-digest algorithm, RFC--1321. Network Working Group, IETF, April 1992.
• 36: 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]
• 37: P. Thambidurai and Y.-K. Park. Interactive consistency with multiple failure modes. Symposium on Reliable Distributed Systems, pages 93--100. IEEE, 1988.
• 38: R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. Symposium on Operating Systems Design and Implementation, pages 91--104. USENIX Association, 2004.
• 39: X. Wang, D. Feng, X. Lai, and H. Yu. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. Report 2004/199. Cryptology ePrint Archive, August 2004. http://eprint.iacr.org/.
• 40: A. Wool. Quorum systems in replicated databases: science or fiction. Bull. IEEE Technical Committee on Data Engineering, 21(4):3--11. IEEE, December 1998.
• 41: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Design, Reliability, Security

Keywords:
byzantine fault-tolerance, fault-scalability, quorums, replicated state machines, services