000172447 001__ 172447
000172447 005__ 20181203022558.0
000172447 0247_ $$2doi$$a10.1007/s00446-010-0103-7
000172447 02470 $$2ISI$$a000280921100001
000172447 037__ $$aARTICLE
000172447 245__ $$aRefined quorum systems
000172447 269__ $$a2010
000172447 260__ $$c2010
000172447 336__ $$aJournal Articles
000172447 520__ $$aIt is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contention. This paper initiates the first study of quorum systems that help design such implementations by encompassing, at the same time, optimal resilience, as well as optimal best-case complexity. We introduce the notion of a refined quorum system (RQS) of some set S as a set of three classes of subsets (quorums) of S: first class quorums are also second class quorums, themselves being also third class quorums. First class quorums have large intersections with all other quorums, second class quorums typically have smaller intersections with those of the third class, the latter simply correspond to traditional quorums. Intuitively, under uncontended and synchronous conditions, a distributed object implementation would expedite an operation if a quorum of the first class is accessed, then degrade gracefully depending on whether a quorum of the second or the third class is accessed. Our notion of refined quorum system is devised assuming a general adversary structure, and this basically allows algorithms relying on refined quorum systems to relax the assumption of independent process failures, often questioned in practice. We illustrate the power of refined quorums by introducing two new optimal Byzantine-resilient distributed object implementations: an atomic storage and a consensus algorithm. Both match previously established resilience and best-case complexity lower bounds, closing open gaps, as well as new complexity bounds we establish here. Each of our algorithms is representative of a different class of architectures, highlighting the generality of the refined quorum abstraction.
000172447 6531_ $$aQuorums
000172447 6531_ $$aAtomic storage
000172447 6531_ $$aConsensus
000172447 6531_ $$aComplexity
000172447 6531_ $$aByzantine failures
000172447 6531_ $$aConsensus
000172447 6531_ $$aObjects
000172447 6531_ $$aMemory
000172447 6531_ $$aPaxos
000172447 6531_ $$aTime
000172447 700__ $$0240335$$g105326$$uEcole Polytech Fed Lausanne, Sch Comp & Commun Sci, CH-1015 Lausanne, Switzerland$$aGuerraoui, Rachid
000172447 700__ $$aVukolic, Marko$$uIBM Res Zurich, Ruschlikon, Switzerland
000172447 773__ $$j23$$tDistributed Computing$$q1-42
000172447 909C0 $$xU10407$$0252114$$pDCL
000172447 909CO $$pIC$$particle$$ooai:infoscience.tind.io:172447
000172447 937__ $$aEPFL-ARTICLE-172447
000172447 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000172447 980__ $$aARTICLE