Crumbling walls

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Crumbling walls: a class of practical and efficient quorum systems

Full text

Pdf (1.04 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing table of contents

Ottowa, Ontario, Canada

Pages: 120 - 129

Year of Publication: 1995

ISBN:0-89791-710-3

Authors

David Peleg	Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel
Avishai Wool	Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 27, Citation Count: 15

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/224964.224978 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ADKM92	Y. Amir, D. Dolev, S. Kramer, and D. Malki. Transis: A communication subsystem for high availability. In Proc. ~~nd Inter. Syrup. Fault- Tolerant Comp. Sys., pages 76-84, 1992.
	AE91	Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991 [doi>10.1145/103727.103728]
	BG87	D. Barbara , H. Garcia-Molina, The reliability of voting mechanisms, IEEE Transactions on Computers, v.36 n.10, p.1197-1208, Oct. 1987 [doi>10.1109/TC.1987.1676860]
	CAA90	Shun Yan Cheung , Mostafa H. Ammar , Mustaque Ahamad, The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data, Proceedings of the Sixth International Conference on Data Engineering, p.438-445, February 05-09, 1990
	Con	N. Condorcet. Essai sur l'application de l'analyse ~ la probabilit~ des decisions rendues k la pluralite des voix. Paris, 1785.
	DGS85	Susan B. Davidson , Hector Garcia-Molina , Dale Skeen, Consistency in a partitioned network: a survey, ACM Computing Surveys (CSUR), v.17 n.3, p.341-370, Sept. 1985 [doi>10.1145/5505.5508]
	DKK+94	Krzysztof Diks , Evangelos Kranakis , Danny Krizanc , Bernard Mans , Andrzej Pelc, Optimal coteries and voting schemes, Information Processing Letters, v.51 n.1, p.1-6, July 12, 1994 [doi>10.1016/0020-0190(94)00064-6]
	EL75	P. ErdSs and L. Lov~sz. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, pages 609-627. Colloq. Math. Soc. J~nos Bolyai 10, 1975.
	GB85	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]
	Gif79	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]
	Her84	M. P. Herlihy, REPLICATION METHODS FOR ABSTRACT DATA TYPES, Massachusetts Institute of Technology, Cambridge, MA, 1984
	HMP95	Ron Holzman , Yosi Marcus , David Peleg, Load Balancing in Quorum Systems (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.38-49, August 16-18, 1995
	HR90	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	IK93	T. Ibaraki , T. Kameda, A Theory of Coteries: Mutual Exclusion in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.779-794, July 1993 [doi>10.1109/71.238300]
	KC91	Akhil Kumar , Shun Yan Cheung, A high availability N hierarchical grid algorithm for replicated data, Information Processing Letters, v.40 n.6, p.311-316, Dec. 30, 1991 [doi>10.1016/0020-0190(91)90199-R]
	Knu68	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	KRS93	A. Kumar, M. Rabinovich, and R. K. Sinha. A performance study of general grid structures for replicated data. In Proc. Inter. Conf. Dist. Comp. Sys., 1993.
	Kum91	Akhil Kumar, Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data, IEEE Transactions on Computers, v.40 n.9, p.996-1004, September 1991 [doi>10.1109/12.83661]
	Lov73	L. Lov~sz. Coverings and colorings of hypergraphs. In Proc. ~th Southeastern Con/. Combinatorics, Graph Theory and Computing, pages 3-12, 1973.
	Mae85	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]
	MP92a	Y. Marcus and D. Peleg. Construction methods for quorum systems. Technical Report CS92- 33, The Weizrnann Institute of Science, Rehovot, Israel, 1992.
	MP92b	Y. Marcus and D. Peleg. Load balancing in quorum systems. Technical Report CS92-34, The Weizmann Institute of Science, Rehovot, Israel, 1992.
	MV88	S.J. Mullender and P. M. B. Vit~nyi. Distributed match-making. Algorithmica, 3:367- 391, 1988.
	Nei92	Mitchell L. Neilsen, Quorum structures in distributed systems, Kansas State University, Manhattan, KS, 1992
	NW94	M. Naor and A. Wool. The load, capacity and availability of quorum systems. In Proc. 35th IEEE Syrup. Found. o/Comp. Science, pages 214-225, 1994.
	NW95a	M. Naor , A. Wool, The Load, Capacity and Availability of Quorum Systems, Weizmann Science Press of Israel, Jerusalem, Israel, 1995
	NW95b	M. Naor and A. Wool. Access control and signatures via quorum secret sharing, 1995. Manuscript.
	PW93	D. Peleg , A. Wool, The Availability of Quorum Systems, Weizmann Science Press of Israel, Jerusalem, Israel, 1993
	PW94	D. Peleg , A. Wool, Crumbling Walls: A Class of High Availability Quorum Systems, Weizmann Science Press of Israel, Jerusalem, Israel, 1994
	Ray86	M. Raynal , D. Beeson, Algorithms for mutual exclusion, MIT Press, Cambridge, MA, 1986
	RST92	Sampath Rangarajan , Sanjeev Setia , Satish K. Tripathi, A Fault-Tolerant Algorithm for Replicated Data Management, Proceedings of the Eighth International Conference on Data Engineering, p.230-237, February 03-07, 1992
	RT91	Sampath Rangarajan , Satish K. Tripathi, A Robust Distributed Mutual Exclusion Algorithm, Proceedings of the 5th International Workshop on Distributed Algorithms, p.295-308, October 07-09, 1991
	SB94	M. Spasojevic , P. Berman, Voting as the Optimal Static Pessimistic Scheme for Managing Replicated Data, IEEE Transactions on Parallel and Distributed Systems, v.5 n.1, p.64-73, January 1994 [doi>10.1109/71.262589]
	Tho79	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]
	YG94	Tak W. Yan , Hector Garcia-Molina, Distributed selective dissemination of information, Proceedings of the third international conference on on Parallel and distributed information systems, p.89-98, October 1994, Autin, Texas, United States

CITED BY 15

	Dahlia Malkhi , Michael Reiter , Rebecca Wright, Probabilistic quorum systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.267-273, August 21-24, 1997, Santa Barbara, California, United States
	Guohong Cao , Mukesh Singhal, A Delay-Optimal Quorum-Based Mutual Exclusion Algorithm for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.12, p.1256-1268, December 2001
	Moni Naor , Avishai Wool, Access control and signatures via quorum secret sharing, Proceedings of the 3rd ACM conference on Computer and communications security, p.157-168, March 14-15, 1996, New Delhi, India
	Rida A. Bazzi, Synchronous Byzantine quorum systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.259-266, August 21-24, 1997, Santa Barbara, California, United States
	David Peleg , Avishai Wool, How to be an efficient snoop, or the probe complexity of quorum systems (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.290-299, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Zygmunt J. Haas , Ben Liang, Ad Hoc mobility management with uniform quorum systems, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.228-240, April 1999
	Govind Krishnamurthi , Murat Azizoğlu , Arun K. Somani, Optimal location management algorithms for mobile networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.223-232, October 25-30, 1998, Dallas, Texas, United States
	Roger Wattenhofer , Peter Widmayer, An inherent bottleneck in distributed counting, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.159-167, August 21-24, 1997, Santa Barbara, California, United States
	Ravi Prakash , Zygmunt Haas , Mukesh Singhal, Load-balanced location management for cellular mobile systems using quorums and dynamic hashing, Wireless Networks, v.7 n.5, p.497-512, September 2001
	Fatima Belkouch , Marc Bui , Liming Chen , Ajoy K. Datta, Self-stabilizing deterministic network decomposition, Journal of Parallel and Distributed Computing, v.62 n.4, p.696-714, April 2002
	Ing-Ray Chen , Ding-Chau Wang , Chih-Ping Chu, Analyzing User-Perceived Dependability and Performance Characteristics of Voting Algorithms for Managing Replicated Data, Distributed and Parallel Databases, v.14 n.3, p.199-219, November 2003
	Rida A. Bazzi, Synchronous Byzantine quorum systems, Distributed Computing, v.13 n.1, p.45-52, January 2000
	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
	Ada Wai-Chee Fu , Yat Sheung Wong , Man Hon Wong, Diamond Quorum Consensus for High Capacity and Efficiency in a Replicated Database System, Distributed and Parallel Databases, v.8 n.4, p.471-492, Oct. 2000
	Akhil Kumar, An Efficient SuperGrid Protocol for High Availability and Load Balancing, IEEE Transactions on Computers, v.49 n.10, p.1126-1133, October 2000