{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T05:11:24Z","timestamp":1791263484420,"version":"4.1.0"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>Given a strategy to pick quorums, the load LS is the minimal access probability of the busiest element, minimizing over the strategies. The capacity \\capS\\ is the highest quorum accesses rate that cS can handle, so $\\capS=1\/\\LS$.<\/jats:p>\n                  <jats:p>The availability of a quorum system cS is the probability that at least one quorum survives, assuming that each element fails independently with probability p. A tradeoff between LS and the availability of cS is shown.<\/jats:p>\n                  <jats:p>We present four novel constructions of quorum systems, all featuring optimal or near optimal load, and high availability. The best construction, based on paths in a grid, has a load of $O(1\/\\sqn)$, and a failure probability of $\\exp(-\\Omega(\\sqn))$ when the elements fail with probability $p &lt; \\half$. Moreover, even in the presence of faults, with exponentially high probability the load of this system is still $O(1\/\\sqn)$. The analysis of this scheme is based on percolation theory.<\/jats:p>","DOI":"10.1137\/s0097539795281232","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"423-447","source":"Crossref","is-referenced-by-count":127,"title":["The Load, Capacity, and Availability of Quorum Systems"],"prefix":"10.1137","volume":"27","author":[{"given":"Moni","family":"Naor","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avishai","family":"Wool","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/103727.103728"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"R. Aharoni, P. Erd\u00f6s, and N. Linial,\n                      Dual integer linear programs and the relationship between their optima\n                      , in Proc. 17th ACM Symp. Theory of Computing, 1985, pp. 476\u2013483.","DOI":"10.1145\/22145.22198"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206313"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676860"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Y. Cheung, M. H. Ammar, and M. Ahamad,\n                      The grid protocol: A high performance scheme for maintaining replicated data\n                      , in Proc. 6th IEEE Int. Conf. Data Engineering, 1990, pp. 438\u2013445.","DOI":"10.1109\/ICDE.1990.113497"},{"key":"R6","unstructured":"N. Condorcet,\n                      Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des decisions rendues \u00e0 la pluralite des voix\n                      , Paris, 1785."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/5505.5508"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Dubiner and U. Zwick,\n                      Amplification and percolation\n                      , in Proc. 33rd IEEE Symp. Foundations of Comp. Sci. (FOCS), 1992, pp. 258\u2013267.","DOI":"10.1109\/SFCS.1992.267766"},{"key":"R9","first-page":"609","volume":"10","author":"Erd\u00f6s P.","year":"1975","journal-title":"Colloq. Math. Soc. J\u00e1nos Bolyai"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01864160"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4223"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"D. K. Gifford,\n                      Weighted voting for replicated data\n                      , in Proc. 7th Symp. Oper. Sys. Princip., 1979, pp. 150\u2013159.","DOI":"10.1145\/800215.806583"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"G. R. Grimmett,\n                      Percolation\n                      , Springer\u2010Verlag, 1989.","DOI":"10.1007\/978-1-4757-4208-4"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90120-4"},{"key":"R18","unstructured":"M. P. Herlihy,\n                      Replication Methods for Abstract Data Types\n                      , PhD thesis, Massachusetts Institute of Technology, MIT\/LCS\/TR\u2010319, 1984."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Holzman, Y. Marcus, and D. Peleg,\n                      Load balancing in quorum systems\n                      , in Proc. 4th Workshop on Algorithms and Data Structures, Kingston, Ont., Canada, 1995, pp. 38\u201349, SIAM J. Discrete Math, to appear.","DOI":"10.1007\/3-540-60220-8_49"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/32.238570"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01197577"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/12.83661"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90199-R"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"A. Kumar, M. Rabinovich, and R. K. Sinha,\n                      A performance study of general grid structures for replicated data\n                      , in Proc. 13th Inter. Conf. Dist. Comp. Sys., 1993, pp. 178\u2013185.","DOI":"10.1109\/ICDCS.1993.287710"},{"key":"R26","unstructured":"L. Lov\u00e1sz,\n                      Coverings and colorings of hypergraphs\n                      , in Proc. 4th Southeastern Conf. Combinatorics, Graph Theory and Computing, 1973, pp. 3\u201312."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970203"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/214438.214445"},{"key":"R29","unstructured":"Y. Marcus and D. Peleg,\n                      Construction methods for quorum systems\n                      , Tech. Report CS92\u201333, The Weizmann Institute of Science, Rehovot, Israel, 1992."},{"key":"R30","unstructured":"T. R. Mathies,\n                      Percolation theory and computing with faulty arrays of processors\n                      , in Proc. 3rd ACM\u2010SIAM Symp. on Discrete Alg., 1992, pp. 100\u2013103."},{"key":"R31","first-page":"856","volume":"33","author":"Menshikov M. V.","year":"1986","journal-title":"Soviet Mathematics Doklady","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762123"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"M. Naor and A. Wool,\n                      The load, capacity and availability of quorum systems\n                      , in Proc. 35th IEEE Symp. Foundations of Comp. Sci. (FOCS), 1994, pp. 214\u2013225.","DOI":"10.1109\/SFCS.1994.365692"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"M. Naor and A. Wool,\n                      Access control and signatures via quorum secret sharing\n                      , in Proc. 3rd ACM Conf. Comp. and Comm. Security, New Delhi, India, 1996, pp. 157\u2013168. Also available as Theory of Cryptography Library record 96\u201008,\n                      http:\/\/theory.lcs.mit.edu\/\u223ctcryptol\/1996.html\n                      .","DOI":"10.1145\/238168.238209"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1169"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00016-9"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050027"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"Sampath Rangarajan, Satish Tripathi, A robust distributed mutual exclusion algorithm, Lecture Notes in Comput. Sci., Vol. 579, Springer, Berlin, 1992, 295\u20133081229516","DOI":"10.1007\/BFb0022455"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1145\/358527.358537"},{"key":"R40","unstructured":"A. Skhrei\u02d8ver, Teoriya lineinogo i tselochislennogo programmirovaniya. 2, \u201cMir\u201d, 1991, 361\u2013704, Translated from the English by S. A. Tarasov, M. A. Frumkin and V. I. Shlyk; Translation edited by L. G. Khachiyan94g:90005"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1109\/71.262589"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1145\/320071.320076"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90016-6"},{"key":"R44","unstructured":"C. Wu,\n                      Replica control protocols that guarantee high availability and low access cost\n                      , Tech. Report 1817, Dept. Computer Science, Universirt of Illinois, Urbana\u2010Champaign, Urbana, Illinois, 1993."},{"key":"R45","doi-asserted-by":"crossref","unstructured":"C. Wu and G. G. Belford,\n                      The triangular lattice protocol: A highly fault tolerant protocol for replicated data\n                      , in Proc. 11th IEEE Symp. on Reliable Dist. Sys., 1992, pp. 66\u201373.","DOI":"10.1109\/RELDIS.1992.235141"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"T. W. Yan and H. Garcia\u2010Molina,\n                      Distributed selective dissemination of information\n                      , in Proc. 3rd Inter. Conf. Par. Dist. Info. Sys., 1994, pp. 89\u201398.","DOI":"10.1109\/PDIS.1994.331728"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795281232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:09Z","timestamp":1787335929000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795281232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795281232"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795281232","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}