On the availability of non-strict quorum systems

Amitanand Aiyer, Lorenzo Alvizi, Rida Bazzi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

32 Scopus citations


Allowing read operations to return stale data with low probability has been proposed as a means to increase availability in quorums systems. Existing solutions that allow stale reads cannot tolerate an adversarial scheduler that can maliciously delay messages between servers and clients in the system and for such a scheduler existing solutions cannot enforce a bound on the staleness of data read. This paper considers the possibility of increasing system availability while at the same time tolerating a malicious scheduler and guaranteeing an upper bound on the staleness of data. We characterize the conditions under which this increase is possible and show that it depends on the ratio of the write frequency to the servers' failure frequency. For environments with a relatively large failure frequency compared to write frequency, we propose K-quorums that can provide higher availability than the strict quorum systems and also guarantee bounded staleness. We also propose a definition of k-atomicity and present a protocol to implement a k-atomic register using k-quorums.

Original languageEnglish (US)
Title of host publicationDistributed Computing - 19th International Conference, DISC 2005, Proceedings
Number of pages15
StatePublished - 2005
Event19th International Conference on Distributed Computing, DISC 2005 - Cracow, Poland
Duration: Sep 26 2005Sep 29 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3724 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Conference on Distributed Computing, DISC 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the availability of non-strict quorum systems'. Together they form a unique fingerprint.

Cite this