Probabilistic Quorum SystemsDahlia MalkhiMichael Reiter Rebecca WrightAT&T Labs—Research180 Park Avenue, Florham Park, NJ 07932-0971{dalia,reiter,rwright} @2research.att.comAbctractServicesreplicated using a quorum Bystem allow operationsto be performed at only a subset (quorum) of the servers,and ensure consistency among operatiom by requiring thatany two quorums intersect. In this paper we explore the con-sequences of mqukingthis intersection property to hold onlywith very high probsbilit y. We show that doing so can offerdramatic improvements in the performance and avaiiabtityof the service, both for services tolerant of benign server fail-ures and services tolerant of arbitrary (Byzantine) ones. Wealso prove a lower bound on the performance that can beachieved with this technique.1 IntroductionQuomms are tools for increasing the availability and effi-aency of replicated services. A guorum system is a set ofsubsets of servers, every pair of which int eraect. Intuitively,the intersection property guarantees that if a “write” oper-ation is performed at one quorum, and later a ‘Yeadn op-eration at another quorum, then there in some server thatobserves both operations and therefore is able to provide theup-to-date value to the reader. Thus, system-wide consis-tency can be maintained while allowing any quorum to acton behalf of the entire system. Compared with performingevery operation at every mrv-as in the State Machine Ap-proach [Sch90]-using quorums reduces the load on serversand increases service availebilit y despite server crashes.Quorum sygtems have been extensively studied and mea-sured (cf., [Gf19, Tho79, Mae85, GB85, Her86, BG87, ET89,CAA90, AE91, NW94, PW95a, PW95b]). Three meaaurea ofa quorum system will be of particular interest in this papaload ~W94], fault tolerance ~G87], and failure probability(see [BG87, PW95b]). Theload of a quorum system is a mea-sure of its effiaency. Intuitively, the load iu the rate at whichthe busiest server will be accessed. The ~aulttolerance, alsocalled the availability, of a system is the number of serversthat can fail without disabling the system. A related mea-sure is ~ailrmeprobability, the probabfit y that the system isdisabled. (Load, fault tolerance, and failure probability willbe defined preasely in Section 2.) The fault tolerance of anyquorum system is bounded by half of the number of servers.Moreover, as we show in Section 3, there is a tradeoff betweenlow load and good fault-tolerance (and failure probabilityy),and in fact it is impossible to simultaneously achieve bothoptimally.To break these limitations, in this paper we relax theintersection property of a quomm system so that “quorums”Permission to make digitWlmrd copies of rdlor partof this nmhxif!l forpersonal or cl.aswoom use is granted without fm provided thatthe copiessre not made or distributed for profit or conmwwiol Avm[agc,, the copy-righl notice. the title of the publication ond its date nppem’.findnotice isgiven thot copyright is hy permission of the ACM. Inc. Tn copy nlhemvise.10republish, to pat on servws or 10redistrihule to lists. I’CqIIircs specilicPernris..iwlantior fee1997 PO.!X”;97 .Vmlo Barbara C“)I1!S/1Copyright 1997 ACM 0-89791 -952-1 /97/8,. $3. ?(1chosen according to a specified strategy intersect only withvery high probabilityy. We accordingly call these probabilisticguorum .qptems, and henceforth refer to systems that satisfythe original defition of quorums as strict. Probabilisticquorum systems admit the possibtity, albeit small, that twooperations will be performed at non-intersecting quorums, inwhich case consist ency of the system may suf%r.We show, however, that even a small relaxation of con-sistency can yield dramatic improvements in the fault toler-ance and failure probabilityy of the system, while the load re-mains essentially unchanged. Probabtistic quorum systemsare thus most suit able for use when availabiit y of operationsdespite the presence of faults is more important than certainconsistency. This might be the case if the coat of inconsis-tent operations is high but not irrecoverable, or if obtainingthe most up-to-date information is desirable but not criti-cal, while having no information may have heavier penalties.For example, probabilistic quorum systems could be usefulwherever quick access to an answer that is likely to be cor-rect can greatly improve efficiency in the normal case, andthe cost of dealing with incorrect answera when they do oc-cur is not too high. Lampson ~am83] describes this kind ofmechanism as hints, and describes several systems that usesuch hints [LS79, MW77, Smi81]. More recently, hints havebeen used in mobile systems to find more direct routes to thecurrent location of a mobile device [JP96, CP96].1.1 Related WorkThough ours is the first work to study probabilistic quorumsystems as such, the use of replicated variables to give prob-ably correct results has proved usethl in other contexts. Twoexamples of this are used to efiiaently simulate a PRAM us-ing an asynchronous system~PRR92, AR92]. Specifically,Kedem et aL ~PRR92] use a replicated variable in a waythat a correct copy can be reliably identified and probably ex-ists. They then use these variables to crest e a global counterthat processors use to determine whether they are roughlysynchronizedwith other processors, and behave appropri-ately if they are not.Aumann and Rabin [AR92] exhibit aclock construction in an asynchronous system with multipleprocessors that use shared memory to create an object thatcorrectly behaves as a clock with high probabtit y. Theyuse the clock to ensure that processorsstay synchronizedthroughout the computation. In both cases, the protocols toread and write the replicated variables are somewhat com-plex due to the need to detect or mask incorrect copies.Malkhi et al. use essentially a hybrid construction of quo-rums, comb- randomized and deterministic choice of mem-bers, to solve the problem of secure reliable multicast in alarge network with many components ~MR97]. Their workfocuses on a protocol that enforces random choice of mem-bers by involving a set of deterministically chosen processes,whose sise is constant, in every operation. Because of this,if any member of this set faila, the probabilistic “quorums”become inaccessible, in which case their protocol reverts to267strict quorums.Unlike these previous works, which are tailored to spe-cific application requirements, in our work we strive for
View Full Document
Unlocking...