How to be an efficient snoop, or the probe complexity of quorum systems (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How to be an efficient snoop, or the probe complexity of quorum systems (extended abstract)

Full text

Pdf (1.10 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 290 - 299

Year of Publication: 1996

ISBN:0-89791-800-2

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

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 10

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/248052.248112 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.

	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]
	BI87	M. Blum and It. Impa~liazzo. Generic oracles and oracle classes. In Proc. ~~Sth IEEE S~tmp. Found. of Comp. Science, pages 1 } 8-126, 1987.
	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
	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]
	EL75	P. Erd6s and L. Lov~sz. Problems and results on 3-chromatic hypergraphs ~nd some related questions. In Infinite and Finite Sets, pages 609-627. Colloq. Math. Soc. J~nos Bolyai 10, 1975.
	Fu90	Wai Chee Ada Fu, Enhancing concurrency and availability for database systems, Simon Fraser University, Burnaby, BC, Canada, 1992
	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, SIAM Journal on Discrete Mathematics, v.10 n.2, p.223-245, May 1997 [doi>10.1137/S0895480193260303]
	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
	KSS84	J. Kahn, M. Saks, and D. Sturtevant. A topological approach to evasiveness. Combinatorica, 4:297-306, 1984.
	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]
	Loe94	D. E. Loeb, A new proof of Monjardet's median theorem, Journal of Combinatorial Theory Series A, v.73 n.1, p.130-141, Jan. 1996 [doi>10.1006/jcta.1996.0007]
	Lov73	L. Lovlsz. Coverings and colorings of hypergraphs. In Proc. ~th Southeastern Conf. Combinatorics, Graph Theorit 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]
	Mon72	B. Monjardet. Charact6risation des 616ments ipsoduaux du treillis distributif libre. C'. R. A cad. Sc. Paris, sdrie A, 274:12-15, 1972.
	MV88	S.J. Mullender and P. M. B. Vit~inyi. Distributed match-making. Algorithmica, 3:367-391, 1988.
	MYK94	Daniel A. Menascé , Yelena Yesha , Konstantinos Kalpakis, On a Unified Framework for the Evaluation of Distributed Quorum Attainment Protocols, IEEE Transactions on Software Engineering, v.20 n.11, p.868-884, November 1994 [doi>10.1109/32.368122]
	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 Sitmp. Found. o)e Comp. Science, pages 214- 225, 1994.
	NW96	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 [doi>10.1145/238168.238209]
	Owe82	G. Owen. Game Theory. Academic Press, second edition, 1982.
	PW95a	David Peleg , Avishai Wool, The availability of quorum systems, Information and Computation, v.123 n.2, p.210-223, Dec. 1995 [doi>10.1006/inco.1995.1169]
	PW95b	David Peleg , Avishai Wool, Crumbling walls: a class of practical and efficient quorum systems, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.120-129, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224978]
	PW96	David Peleg , Avishai Wool, The availability of crumbling wall quorum systems, Discrete Applied Mathematics, v.74 n.1, p.69-83, April 4, 1997 [doi>10.1016/S0166-218X(96)00016-9]
	Ram90	K. G. Ramamurthy. Coherent Structures and Simple Games. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1990.
	Ray86	M. Raynal , D. Beeson, Algorithms for mutual exclusion, MIT Press, Cambridge, MA, 1986
	Ros73	Arnold L. Rosenberg, On the time required to recognize properties of graphs: a problem, ACM SIGACT News, v.5 n.4, p.15-16, October 1973 [doi>10.1145/1008299.1008302]
	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
	RV76	R.L. Rivest and J. Vuillemin. On recognizing graph properties from adjacency matrices. Theoratical Comp. Science, 3:371-384, 1976.
	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]
	Tuz85	Zs. Tuza. Critical hypergraphs and intersecting set-pair systems. J. Comb. Theory, Series B, 39:134-145, 1985.
	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 10

	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
	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
	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
	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
	Marcelo Moraes de Azevedo , Douglas M. Blough, Multistep Interactive Convergence: An Efficient Approach to the Fault-Tolerant Clock Synchronization of Large Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.9 n.12, p.1195-1212, December 1998
	Tiko Kameda , Feng Xiao , Malika Guerni-Mahoui, Average probe complexity of non-dominated coteries (brief announcement), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.340, July 16-19, 2000, Portland, Oregon, United States
	Rida A. Bazzi, Synchronous Byzantine quorum systems, Distributed Computing, v.13 n.1, p.45-52, January 2000
	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
	Rida A. Bazzi, Access cost for asynchronous Byzantine quorum systems, Distributed Computing, v.14 n.1, p.41-48, January 2001
	Haifeng Yu, Signed quorum systems, Distributed Computing, v.18 n.4, p.307-323, March 2006