Scalable and dynamic quorum systems

ABSTRACT

We investigate issues related to the probe complexity of quorum systems and their implementation in a dynamic environment. Our contribution is twofold. The first regards the algorithmic complexity of finding a quorum in case of random failures. We show a tradeoff between the load of a quorum system and its probe complexity for non adaptive algorithms. We analyze the algorithmic probe complexity of the Paths quorum system suggested by Naor and Wool in [18], and present two optimal algorithms. The first is a non adaptive algorithm that matches our lower bound. The second is an adaptive algorithm with a probe complexity that is linear in the minimum between the size of the smallest quorum set and the inverse of the load of the system. We supply a constant degree network in which these algorithms could be executed efficiently. Thus the Paths quorum system is shown to have good balance between many measures of quality. Our second contribution is presenting Dynamic Paths-a suggestion for a dynamic and scalable quorum system, which can operate in an environment where elements join and leave the system. The quorum system could be viewed as a dynamic adaptation of the Paths system, and therefore has low load high availability and good probe complexity. We show that it scales gracefully as the number of elements grows.

REFERENCES

• 1: Divyakant Agrawal, Omer Egecioglu, and Amr E1 Abbadi. Billiard quorums on the grid. Information Processing Letters, 64(1):9--16, 1997.
• 2: Rida A. Bazzi, Planar Quorums, Proceedings of the 10th International Workshop on Distributed Algorithms, p.251-268, October 09-11, 1996
• 3: M. Bearden , R. P. Bianchini Jr, A Fault-Tolerant Algorithm for Decentralized On-line Quorum Adaptation, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.262, June 23-25, 1998
• 4: Itai Benjamini. Private communication.
• 5: Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
• 6: Oded Goldreich. Randomized Methods in Computation-Lecture Notes. http://www.wisdom.weizmann.ac.il/~oded/rnd.html, 2001.
• 7: Geoffrey Grimmett. Percolation. Springer-Verlag, 1989.
• 8: Yehuda Hassin , David Peleg, Average probe complexity in quorum systems, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.180-189, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384014]
• 9: S. Jajodia , David Mutchler, Dynamic voting algorithms for maintaining the consistency of a replicated database, ACM Transactions on Database Systems (TODS), v.15 n.2, p.230-280, June 1990 [doi>10.1145/78922.78926]
• 10: Danny Dolev , Idit Keidar , Esti Yeger Lotem, Dynamic voting for consistent primary components, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.63-71, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259424]
• 11: N. A. Lynch , A. A. Shvartsman, Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts, Proceedings of the 27th International Symposium on Fault-Tolerant Computing (FTCS '97), p.272, June 25-27, 1997
• 12: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 13: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 14: Mikhail V. Menshikov. Coincidence of critical points in percolation problems. Soviet Mathematics Doklady, 33:856--859, 1986.
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777421]
• 17: Moni Naor , Avishai Wool, Access Control and Signatures via Quorum Secret Sharing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.9, p.909-922, September 1998 [doi>10.1109/71.722223]
• 18: 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]
• 19: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 20: David Peleg , Avishai Wool, How to Be an Efficient Snoop, or the Probe Complexity of Quorum Systems, SIAM Journal on Discrete Mathematics, v.15 n.3, p.416-433, 2002 [doi>10.1137/S0895480198343819]
• 21: Roberto De Prisco , Alan Fekete , Nancy Lynch , Alex Shvartsman, A dynamic view-oriented group communication service, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.227-236, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277739]
• 22: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 23: Beverly A. Sanders, The information structure of distributed mutual exclusion algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.3, p.284-299, Aug. 1987 [doi>10.1145/24068.28052]
• 24: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Experimentation, Performance