Article

Free access

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

Authors:

David Peleg,

Avishai WoolAuthors Info & Claims

PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing

Pages 290 - 299

https://doi.org/10.1145/248052.248112

Published: 01 May 1996 Publication History

PDF eReader

References

[1]

D. Agrawal and A. EI-Abbadi. An efficient and fault-tolerant solution for distributed mutual exclusion. A CM Trans. Comp. Sys., 9(1):1-20, 1991.

Digital Library

Google Scholar

[2]

D. Barbara and H. Garcia-Molina. The reliability of vote mechanisms. IEEE Trans. Comput., C- 36:1197-1208, October 1987.

Digital Library

Google Scholar

[3]

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.

Digital Library

Google Scholar

[4]

$. Y. Cheung, M. H. Arnmar, and M. Ahamad. The grid protocol: A high performance scheme for maintaining replicated data. in Proc. 6th IEEE Int. Conf. Data Engineering, pages 438- 445, 1990.

Digital Library

Google Scholar

[5]

S.B. Davidson, H. Garcia-Molina, and D. Skeen. Consistency in partitioned networks. A CM Computing Surveys, 17(3)::541-370, 1985.

Digital Library

Google Scholar

[6]

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.

Google Scholar

[7]

A. Fu. Enhancing Concurrency and Availability for Database SFstems. PhD thesis, Simon Fraser University, Burnaby, B.C., Canada, 1990.

Digital Library

Google Scholar

[8]

H. G~rcia-Molina and D. Barbara. How to assign votes in a distributed system. J. A C'M, 32(4):841- 860, 1985.

Digital Library

Google Scholar

[9]

D.K. Gifford. Weighted voting for replicated data. In Proc. 7th S~tmp. Oper. S~ts. Princip., pages 150-159, 1979.

Digital Library

Google Scholar

[10]

M.P. Herlihy. Replication Methods for Abstract Data Types. PhD thesis, Massachusetts Institute of Technology, MiT/LCS/TR-319, 1984.

Digital Library

Google Scholar

[11]

Ft. Holzman, Y. Marcus, and D. Peleg. Load balancing in quorum systems. In Proc. J th Workshop on Algorit&n~a and Data .qtructures~ t(in~gston, Ont., Canada, 1995. To appear in SIAM J. Discrete Math.

Digital Library

Google Scholar

[12]

T. Ibaraki and T. Kameda. A theory of coteries: Mutual exclusion in distributed systems. IEEE Trans. Par. Dist. Sys., 4(7):779-794, 1993.

Digital Library

Google Scholar

[13]

A. Kumar and S. Y. Cheung. A high availability ~ hierarchical grid algorithm for replicated data. inf. Proc. Letters, 40:311-316, 1991.

Digital Library

Google Scholar

[14]

D. E. Knuth. The Art of Computer Programruing, Vol. l--Fundamentai Algorithms. Addison- Wesley, 1968.

Digital Library

Google Scholar

[15]

J. Kahn, M. Saks, and D. Sturtevant. A topological approach to evasiveness. Combinatorica, 4:297-306, 1984.

Crossref

Google Scholar

[16]

A. Kumar. Hierarchical quorum consensus: A new algorithm for managing replicated data. IEEE Trans. Comput., 40(9):996-1004, 1991.

Digital Library

Google Scholar

[17]

D.E. Loeb. A new proof of Monjardet's median theorem, 1994. Manuscript, to appear in J. Comb. Theory, Series A.

Digital Library

Google Scholar

[18]

L. Lovlsz. Coverings and colorings of hypergraphs. In Proc. ~th Southeastern Conf. Combinatorics, Graph Theorit and Computing, pages 3-12, 1973.

Google Scholar

[19]

M. Maekawa. A v/~ algorithm for mutual exclusion in decentralized systems. A CM Trans. Comp. Sits., 3(2):145-159, 1985.

Digital Library

Google Scholar

[20]

B. Monjardet. Charact6risation des 616ments ipsoduaux du treillis distributif libre. C'. R. A cad. Sc. Paris, sdrie A, 274:12-15, 1972.

Google Scholar

[21]

S.J. Mullender and P. M. B. Vit~inyi. Distributed match-making. Algorithmica, 3:367-391, 1988.

Digital Library

Google Scholar

[22]

D. A. Menasc~, Y. Yesha, and K. Kalpakis. On a unified framework for the evaluation of distributed quorum attainment protocols. IEEE Trans. Software Eng., 20(11):868-884, 1994.

Digital Library

Google Scholar

[23]

M.L. Neilsen. Quorum Structures in Distributed Systems. PhD thesis, Dept. Computing and Information Sciences, Kansas State University, 1992.

Digital Library

Google Scholar

[24]

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.

Digital Library

Google Scholar

[25]

M. Naor and A. Wool. Access control and signatures via quorum secret sharing. In Proc. 3rd A CM Conf. Comp. and Comm. Security, New Delhi, India, March 1996. See also Technical Report CS95-19, The Weizmann Institute of Science.

Digital Library

Google Scholar

[26]

G. Owen. Game Theory. Academic Press, second edition, 1982.

Google Scholar

[27]

D. Peleg and A. Wool. The availability of quorum systems. Information and Computation, 123(2):210-223, 1995.

Digital Library

Google Scholar

[28]

D. Peleg and A. Wool. Crumbling walls: A class of practical and efficient quorum systems. In Proc. lgth A CM S!tmp. Princip. o.f Dist. Comp., pages 120-129, Ottawa, Canada, 1995.

Digital Library

Google Scholar

[29]

D. Peleg and A. Wool. The availability of crumbling wall quorum systems. Discrete Applied Math., 1996. To appear.

Digital Library

Google Scholar

[30]

K. G. Ramamurthy. Coherent Structures and Simple Games. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1990.

Google Scholar

[31]

M. Raynal. Algorithms for Mutual Exclusion. MiT press, 1986.

Digital Library

Google Scholar

[32]

A.L. Rosenberg. On the time required to recognize properties of graphs: A problem. SIGA CT News, 5:15-16, 1973.

Digital Library

Google Scholar

[33]

S. Rangaxajan, S. Setia, and S. K. Tripathi. A fault-tolerant algorithm for replicated data management, in Proc. 8th iEEE Int. Conf. Data Engineering, pages 230-237, 1992.

Digital Library

Google Scholar

[34]

R.L. Rivest and J. Vuillemin. On recognizing graph properties from adjacency matrices. Theoratical Comp. Science, 3:371-384, 1976.

Crossref

Google Scholar

[35]

R.H. Thomas. A majority concensus approach to concurrency control for multiple copy databiLses. ACM Trans. Database Sits., 4(2):180-209, 1979.

Digital Library

Google Scholar

[36]

Zs. Tuza. Critical hypergraphs and intersecting set-pair systems. J. Comb. Theory, Series B, 39:134-145, 1985.

Crossref

Google Scholar

[37]

T.W. Yah and H. Garcia-Molina. Distributed selective dissemination of information. In Proc. $rd Inter. Conf. Par. Dist. {nfo. Sys., pages 89- 98, 1994.

Digital Library

Google Scholar

Cited By

View all

(2015)An inclusion hierarchy of irreversible dynamosTheoretical Computer Science10.1016/j.tcs.2015.06.035596:C(1-11)Online publication date: 6-Sep-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.06.035
Kumar VAgarwal A(2011)Multi-dimensional Grid Quorum Consensus for High Capacity and Availability in a Replica Control ProtocolHigh Performance Architecture and Grid Computing10.1007/978-3-642-22577-2_10(67-78)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22577-2_10
Gilbert SLynch NShvartsman A(2010)RamboDistributed Computing10.1007/s00446-010-0117-123:4(225-272)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1007/s00446-010-0117-1
Show More Cited By

Index Terms

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

Recommendations

How to Be an Efficient Snoop, or the Probe Complexity of Quorum Systems

A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication, and dissemination of information.

...
Average probe complexity in quorum systems

This paper discusses the probe complexity of randomized algorithms and the deterministic average case probe complexity for some classes of nondominated coteries, including majority, crumbling walls, tree, wheel and hierarchical quorum systems, and ...
Signed quorum systems
PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

With n servers that independently fail with probability of p < 0.5, it is well known that the majority quorum system achieves the best availability among all quorum systems. However, even this optimal construction requires (n+1)/2 functioning servers ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing

May 1996

344 pages

ISBN:0897918002

DOI:10.1145/248052

Chairmen:
James E. Burns
Bellcore
,
Yoram Moses
Weizmann Institute of Science

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC96

Sponsor:

PODC96: 15th Annual ACM Symposium on Principles of Distributed Computing

May 23 - 26, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

PODC '96 Paper Acceptance Rate 69 of 117 submissions, 59%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
254
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)3

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

(2015)An inclusion hierarchy of irreversible dynamosTheoretical Computer Science10.1016/j.tcs.2015.06.035596:C(1-11)Online publication date: 6-Sep-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.06.035
Kumar VAgarwal A(2011)Multi-dimensional Grid Quorum Consensus for High Capacity and Availability in a Replica Control ProtocolHigh Performance Architecture and Grid Computing10.1007/978-3-642-22577-2_10(67-78)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22577-2_10
Gilbert SLynch NShvartsman A(2010)RamboDistributed Computing10.1007/s00446-010-0117-123:4(225-272)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1007/s00446-010-0117-1
Warns TStorm CTheel O(2009)How to be a More Efficient SnoopProceedings of the 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies10.1109/PDCAT.2009.31(354-359)Online publication date: 8-Dec-2009
https://dl.acm.org/doi/10.1109/PDCAT.2009.31
Yu H(2006)Signed quorum systemsDistributed Computing10.1007/s00446-005-0133-818:4(307-323)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1007/s00446-005-0133-8
Yu HChaudhuri SKutten S(2004)Signed quorum systemsProceedings of the twenty-third annual ACM symposium on Principles of distributed computing10.1145/1011767.1011803(246-255)Online publication date: 25-Jul-2004
https://dl.acm.org/doi/10.1145/1011767.1011803
Bazzi R(2003)Non-blocking Asynchronous Byzantine Quorum SystemsDistributed Computing10.1007/3-540-48169-9_8(109-122)Online publication date: 3-Jun-2003
https://doi.org/10.1007/3-540-48169-9_8
Hassin YPeleg DKshemkalyani AShavit N(2001)Average probe complexity in quorum systemsProceedings of the twentieth annual ACM symposium on Principles of distributed computing10.1145/383962.384014(180-189)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.1145/383962.384014
Bazzi R(2001)Access cost for asynchronous Byzantine quorum systemsDistributed Computing10.1007/PL0000892514:1(41-48)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.1007/PL00008925
Malkhi DReiter MWool AWright R(2001)Probabilistic Quorum SystemsInformation and Computation10.1006/inco.2001.3054170:2(184-206)Online publication date: 11-Nov-2001
https://dl.acm.org/doi/10.1006/inco.2001.3054
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

How to Be an Efficient Snoop, or the Probe Complexity of Quorum Systems

Average probe complexity in quorum systems

Signed quorum systems