A Framework for Dynamic Byzantine StorageJean-Philippe Martin, Lorenzo AlvisiThe University of Texas at AustinNominated for the William Carter AwardDecember 17, 2003AbstractWe present a quorum-based protocol for a Byzantine fault-tolerant storage system that can dynamicallyadapt its failure threshold and server count, allowing the storage system to be reconfigured in anticipationof possible failures or to replace servers as desired. Our protocol provides confirmable wait-free atomicsemantics while tolerating Byzantine failures from the clients or servers. The system can grow withoutbound to tolerate as many failures as desired. Finally, the protocol is optimal and fast: only the minimalnumber of servers—3f + 1— is needed to tolerate any f failures and, in the common case, reads requireonly one message round-trip.1 IntroductionQuorum systems [5] are a valuable tool for building highly available distributed data services. These systemsstore a shared variable at a set of servers and perform read and write operations at some subset of servers (aquorum). To access the shared variable, protocols define some intersection property for the quorums which,combined with the protocol description themselves, ensure that read and write operations obey precise consis-tency semantics. In particular, a shared register can provide, in order of increasing strength, safe, regular oratomic semantics [11].Malkhi and Reiter [13] have pioneered the study of Byzantine quorum systems (BQSs), in which serversmay fail arbitrarily. Their masking quorum systems guarantee data integrity and availability despite compro-mised servers; they also introduce dissemination quorum systems that can be used by services that supportself-verifying data, i.e., data that cannot be undetectably altered by a faulty server, such as data that have beendigitally signed or associated with message authentication codes (MACs).Traditional BQS protocols set two parameters—N, the set of servers in the quorum system, and f, theresilience threshold denoting the maximum number of servers that can be faulty1—and treat them as constants1Papers such as [13] consider generalized fault structures, offering a more general way of characterizing fault tolerance than athreshold. However, such structures remain static.1throughout the life of the system. The rigidity of these static protocols is clearly undesirable.Fixing f forces the administrator to select a conservative value for the resilience threshold, one that cantolerate the worst case-failure scenario. Usually, this scenario will be relatively rare; however, since thevalue of f determines the size of the quorums, in the common case quorum operations are forced to accessunnecessarily large sets, with obvious negative effects on performance.Fixing N not only prevents the system administrator from retiring faulty or obsolete servers and substitutingthem with correct or new ones, but also greatly reduces the advantages of any technique designed to changef dynamically. For a given Byzantine quorum protocol N implicitly determines the maximum value fmaxofthe resilience threshold: in the common case, the degree of replication required to tolerate fmaxfailures iswasted, independent of the value of f that the system uses at a given point in time.Alvisi et al. [2] take a first step towards addressing these limitations. They propose a protocol that candynamically raise or lower f within a range [fmin...fmax] at run time without relying on any concurrencycontrol mechanism (e.g., no locking)—however, their protocol cannot modify N. Improving on this result,Kong et al. [10] propose a protocol that can dynamically adjust f and, once faulty servers are detected, canignore them to obtain quorums that exhibit better load2, effectively shrinking N. The protocol however doesnot allow to add new servers to N. While other quorum-based systems such as Rambo [12], Rambo II [8], andGeoQuorums [6] can adjust dynamically both f and N, they cannot tolerate Byzantine failures.In this paper we propose a methodology for transforming static Byzantine quorum protocols into dynamicones where both N and f can change, growing and shrinking as appropriate during the life of the system3We have successfully applied our methodology to several Byzantine quorum protocols [9, 13, 14, 17, 19].The common characteristic of these protocols is that they are based on the Q-RPC primitive [13]. A Q-RPCcontacts a responsive quorum of servers and collects their answers, and it is a natural building block forimplementing quorum-based read and write operations. Our methodology is simple and non-intrusive: all thatit requires to make a protocol dynamic is to substitute each call to Q-RPC with a call to a new primitive, calledDQ-RPC for dynamic Q-RPC. DQ-RPC maintains the properties of Q-RPC that are critical for the correctnessof Byzantine quorum protocols even when N and f can change.Defining DQ-RPC to minimize changes to existing protocols is challenging. The main difficulty comesfrom proving that read and write operations performed on the dynamic version of a protocol maintain thesame consistency semantics of the operations performed on the static version of the same protocol. In thestatic case, these proofs rely on the intersection properties of the responsive quorums contacted by Q-RPCswhile performing the read and write operations. Unfortunately, these proofs do not carry easily to DQ-RPC.When N changes, it is no longer possible to guarantee quorum intersection: given any two distinct times t12Given a quorum system S, the load of S is the access probability of the busiest quorum in S, minimized over all strategies [18].3We focus on the mechanisms necessary for supporting dynamic quorums. A discussion of the policies used to determine when toadjust N and f is outside the scope of this paper. Some examples of such policies are given in [3, 10].2name can tolerate (crash,Byz) client failures semantics servers requiredcrash (f, 0), without signatures crash atomic 2f + 1U-dissemination [17] (0, b), using signatures crash atomic 3b + 1hybrid-d [9] (f, b), using signatures crash atomic 2f + 3b + 1U-masking [19] (0, b), without signatures correct partial-atomic44b + 1hybrid-m [9] (f, b), without signatures correct partial-atomic42f + 4b + 1Phalanx [14] (0, b), without client signatures Byzantine partial-atomic44b + 1hybrid Phalanx (f, b), without client signatures Byzantine partial-atomic42f + 4b + 1Figure 1: List of quorum protocols
View Full Document
Unlocking...