Quorum placement in networks to minimize access delays

ABSTRACT

A quorum system is a family of sets (themselves called quorums), each pair of which intersect. In many distributed algorithms, the basic unit accessed by a client is a quorum of nodes. Such algorithms are used for applications such as mutual exclusion, data replication, and dissemination of information. However, accessing spread-out quorums causes access delays that we would like to minimize. Furthermore, every member of the quorum incurs processing load to handle quorum accesses by clients.In this paper we study the problem of placing quorums in a physical network so as to minimize the delay that clients incur by accessing quorums, and while respecting each physical node's capacity (in terms of the load of client requests it can handle). We provide approximation algorithms for this problem for two natural measures of delay (the max-delay and total-delay). All our algorithms ensure that each node's load is within a constant factor of its capacity, and minimize delay to within a constant factor of the optimal delay for all capacity-respecting solutions. We also provide better approximations for several well-known quorum systems.

REFERENCES

• 1: Yair Amir , Avishai Wool, Optimal availability quorum systems: theory and practice, Information Processing Letters, v.65 n.5, p.223-228, March 13, 1998 [doi>10.1016/S0020-0190(98)00017-9 ]
• 2: Rida A. Bazzi, Planar quorums, Theoretical Computer Science, v.243 n.1-2, p.243-268, July 28, 2000 [doi>10.1016/S0304-3975(98)00208-4 ]
• 3: Rida A. Bazzi, Access cost for asynchronous Byzantine quorum systems, Distributed Computing, v.14 n.1, p.41-48, January 2001 [doi>10.1007/PL00008925]
• 4: P. Carmi, S. Dolev, S. Har-Peled, M. J. Katz, and M. Segal. Geographic quorum system approximations. Algorithmica, 41(4):233--244, 2005.
• 5: S. Y. Cheung , M. H. Ammar , M. Ahamad, The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.582-592, December 1992 [doi>10.1109/69.180609 ]
• 6: S. Dolev, S. Gilbert, N.A. Lynch, A.A. Shvartsman, and J.L. Welch. Geoquorums: Implementing atomic memory in mobile d hoc networks. In DISC, pages 306--320, 2003.
• 7: Ada Waichee Fu, Delay-Optimal Quorum Consensus for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.8 n.1, p.59-69, January 1997 [doi>10.1109/71.569655 ]
• 8: 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]
• 9: S. Gilbert and G. Malewicz. The quorum deployment problem. In 8th International Conference on Principles of Distributed Systems (OPODIS'04), 2004.
• 10: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 11: Noritaka Kobayashi , Tatsuhiro Tsuchiya , Tohru Kikuno, Minimizing the mean delay of quorum-based mutual exclusion schemes, Journal of Systems and Software, v.58 n.1, p.1-9, August 2001 [doi>10.1016/S0164-1212(01)00023-1 ]
• 12: A. Kumar, M. Rabinovich, and R. K. Sinha. A performance study of general grid structures for replicated data. In Proceedings 13th International Conference on Distributed Computing Systems, pages 178--185, 1993.
• 13: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 14: Xuemin Lin, Delay Optimizations in Quorum Consensus, Proceedings of the 12th International Symposium on Algorithms and Computation, p.575-586, December 19-21, 2001
• 15: 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]
• 16: 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]
• 17: Dahlia Malkhi , Michael K. Reiter , Avishai Wool , Rebecca N. Wright, Probabilistic quorum systems, Information and Computation, v.170 n.2, p.184-206, November 1, 2001 [doi>10.1006/inco.2001.3054 ]
• 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: D. Peleg and A. Wool. Crumbling walls: A class of practical and efficient quorum systems. Distributed Computing, 10(2):87--97, 1997.
• 20: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 21: J.K. Lenstra and A.H.G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26(1):22-35, 1978.
• 22: 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]
• 23: Tatsuhiro Tsuchiya , Masatoshi Yamaguchi , Tohru Kikuno, Minimizing the Maximum Delay for Reaching Consensus in Quorum-Based Mutual Exclusion Schemes, IEEE Transactions on Parallel and Distributed Systems, v.10 n.4, p.337-345, April 1999 [doi>10.1109/71.762814 ]
• 24: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 25: Gerhard J. Woeginger, On the Approximability of Average Completion Time Scheduling under Precedence Constraints, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.887-897, July 08-12, 2001
• 26: Haifeng Yu, Signed quorum systems, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011803]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Performance, Theory

Keywords:
LP rounding, approximation algorithms, location, problems, quorum systems