Scholars@Duke

Write markers for probabilistic quorum systems

Publication ,  Conference
Merideth, MG; Reiter, MK
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
December 1, 2008
Published version (DOI)

Probabilistic quorum systems can tolerate a larger fraction of faults than can traditional (strict) quorum systems, while guaranteeing consistency with an arbitrarily high probability for a system with enough replicas. However, the masking and opaque types of probabilistic quorum systems are hampered in that their optimal load-a best-case measure of the work done by the busiest replica, and an indicator of scalability-is little better than that of strict quorum systems. In this paper we present a variant of probabilistic quorum systems that uses write markers in order to limit the extent to which Byzantine-faulty servers act together. Our masking and opaque probabilistic quorum systems have asymptotically better load than the bounds proven for previous masking and opaque quorum systems. Moreover, the new masking and opaque probabilistic quorum systems can tolerate an additional 24% and 17% of faulty replicas, respectively, compared with probabilistic quorum systems without write markers. © 2008 Springer Berlin Heidelberg.

Duke Scholars

Michael Reiter
Author Michael Reiter Computer Science

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

10.1007/978-3-540-92221-6_3

EISSN

1611-3349

ISSN

0302-9743

Publication Date

December 1, 2008

Volume

5401 LNCS

Start / End Page

5 / 21

Related Subject Headings

  • Artificial Intelligence & Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Merideth, M. G., & Reiter, M. K. (2008). Write markers for probabilistic quorum systems. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 5401 LNCS, pp. 5–21). https://doi.org/10.1007/978-3-540-92221-6_3
Merideth, M. G., and M. K. Reiter. “Write markers for probabilistic quorum systems.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5401 LNCS:5–21, 2008. https://doi.org/10.1007/978-3-540-92221-6_3.
Merideth MG, Reiter MK. Write markers for probabilistic quorum systems. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008. p. 5–21.
Merideth, M. G., and M. K. Reiter. “Write markers for probabilistic quorum systems.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5401 LNCS, 2008, pp. 5–21. Scopus, doi:10.1007/978-3-540-92221-6_3.
Merideth MG, Reiter MK. Write markers for probabilistic quorum systems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008. p. 5–21.

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

10.1007/978-3-540-92221-6_3

EISSN

1611-3349

ISSN

0302-9743

Publication Date

December 1, 2008

Volume

5401 LNCS

Start / End Page

5 / 21

Related Subject Headings

  • Artificial Intelligence & Image Processing