Refined quorum systems

ABSTRACT

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contention. This paper initiates the first study of quorum systems that help design such implementations by encompassing, at the same time, optimal resilience (just like traditional quorum systems), as well as optimal best-case complexity (unlike traditional quorum systems).

We introduce the notion of a refined quorum system (RQS) of some set S as a set of three classes of subsets (quorums) of S: firstclass quorums are also second class quorums, themselves being also third class quorums. First class quorums have large intersections with all other quorums, second class quorums typically have smaller intersections with those of the third class, the latter simply correspond to traditional quorums. Intuitively, under uncontended and synchronous conditions, a distributed object implementation would expedite an operation if a quorum of the first class is accessed, then degrade gracefully depending on whether a quorum of the second or the third class is accessed. Our notion of refined quorum system is devised assuming a general adversary structure, and this basically allows relying on refined quorum systems to relax the assumption of independent process failures, often questioned in practice.

We illustrate the power of refined quorums by introducing two new optimal Byzantine-resilient distributed object implementations: anatomic storage and a consensus algorithm. Both match previously established resilience and best-case complexity lower bounds, closing open gaps, as well as new complexity bounds we establish here.

REFERENCES

• 1: Michael Abd-El-Malek , Gregory R. Ganger , Garth R. Goodson , Michael K. Reiter , Jay J. Wylie, Fault-scalable Byzantine fault-tolerant services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 2: I. Abraham, G. V. Chockler, I. Keidar, and D. Malkhi. Byzantine disk paxos: optimal resilience with Byzantine shared memory. Distributed Computing, 18(5):387--408, 2006.
• 3: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
• 4: John Black , Shai Halevi , Hugo Krawczyk , Ted Krovetz , Phillip Rogaway, UMAC: Fast and Secure Message Authentication, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.216-233, August 15-19, 1999
• 5: 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
• 6: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 7: G. Chockler, R. Guerraoui, and I. Keidar. On the space requirements of robust storage implementations. In Dagstuhl Seminar From Security to Dependability, September 2006.
• 8: James Cowling , Daniel Myers , Barbara Liskov , Rodrigo Rodrigues , Liuba Shrira, HQ replication: a hybrid quorum protocol for byzantine fault tolerance, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.13-13, November 06-08, 2006, Seattle, WA
• 9: P. Dutta, R. Guerraoui, and M. VukoliĆ. Best-case complexity of asynchronous Byzantine consensus. Technical Report 200499, Swiss Federal Institute of Technology (EPFL), School of Computer and Communication Sciences, Lausanne, Switzerland, 2005.
• 10: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 11: 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]
• 12: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 13: Daniel Golovin , Anupam Gupta , Bruce M. Maggs , Florian Oprea , Michael K. Reiter, Quorum placement in networks: minimizing network congestion, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146388]
• 14: Garth R. Goodson , Jay J. Wylie , Gregory R. Ganger , Michael K. Reiter, Efficient Byzantine-Tolerant Erasure-Coded Storage, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.135, June 28-July 01, 2004
• 15: Rachid Guerraoui , Ron R. Levy , Marko Vukolic, Lucky Read/Write Access to Robust Atomic Storage, Proceedings of the International Conference on Dependable Systems and Networks, p.125-136, June 25-28, 2006 [doi>10.1109/DSN.2006.50]
• 16: Rachid Guerraoui , Marko Vukolić, How fast can a very robust read be?, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146419]
• 17: R. Guerraoui and M. Vukolić. Refined quorum systems. Technical Report LPD-REPORT-2007-002, Swiss Federal Institute of Technology (EPFL), School of Computer and Communication Sciences, Lausanne, Switzerland, February 2007.
• 18: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 19: 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]
• 20: Martin Hirt , Ueli Maurer, Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.25-34, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259412]
• 21: Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998 [doi>10.1145/278298.278305]
• 22: Flavio P. Junqueira , Keith Marzullo, Synchronous Consensus for Dependent Process Failures, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.274, May 19-22, 2003
• 23: L. Lamport. On interprocess communication. Distributed computing, 1(1):77--101, May 1986.
• 24: 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]
• 25: L. Lamport. Lower bounds for asynchronous consensus. In Future Directions in Distributed Computing, Springer Verlag (LNCS), pages 22--23, 2003.
• 26: L. Lamport. Fast Paxos. Distributed Computing, 19(2):79--103, 2006.
• 27: 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]
• 28: N. A. Lynch and M. R.Tuttle. An introduction to I/O automata. CWI Quarterly, 2(3):219--246, 1989.
• 29: Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Distributed Computing, v.11 n.4, p.203-213, October 1998 [doi>10.1007/s004460050050]
• 30: Jean-Philippe Martin , Lorenzo Alvisi, Fast Byzantine Consensus, IEEE Transactions on Dependable and Secure Computing, v.3 n.3, p.202-215, July 2006 [doi>10.1109/TDSC.2006.35]
• 31: 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
• 32: M. Naor and A. Wool. The load, capacity and availability of quorum systems. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 214--225, 1994.
• 33: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 34: H. V. Ramasamy and C. Cachin. Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast. In Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS 2005), Lecture Notes in Computer Science, pages 88--102, December 2005.
• 35: 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]
• 36: Y. Saito, S. Frolund, A. Veitch, A. Merchant, and S. Spence. Fab: building distributed enterprise disk arrays from commodity components. SIGOPS Oper. Syst. Rev., 38(5):48--58, 2004.
• 37: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 38: Jian Yin , Jean-Philippe Martin , Arun Venkataramani , Lorenzo Alvisi , Mike Dahlin, Separating agreement from execution for byzantine fault tolerant services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 39: P. ZieliƊski. Optimistically terminating consensus. Technical Report UCAM-CL-TR-668, Cambridge University, Cambridge, UK, June 2006.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
arbitrary failures, complexity, consensus, quorums, shared-memory emulations