1CS 395T: Design and Implementation of Trusted ServicesQuorum SystemsNavendu JainOutline Motivation Quorum Systems Tree Quorums Probabilistic Quorum SystemsOutline Motivation Quorum Systems Tree Quorums Probabilistic Quorum SystemsIntroduction Object stored on a single serverRequestReply2Introduction Object stored on a single serverWhat if the server fails ?RequestReplyXIntroduction Replicate the object• Availability• PerformanceRequestReplyIntroduction Replicate the object• Availability• PerformanceBut what about consistency(failures, msg reordering) ?RequestReplyQuorum Systems Client only needs a quorum ofservers to access the objectRequestReply3Quorum Systems Client only needs a quorum ofservers to access the objectExample of a QuorumRequestReplyQuorum Systems Client only needs a quorum ofservers to access the objectAnother QuorumRequestReplyOutline Motivation Quorum Systems Tree Quorums Probabilistic Quorum SystemsQuorum SystemsDefinitionGiven a set of serversA quorum system is a set of subsets ofsuch thatEach is called a quorum 2121:, QQQQ IP2},,{1 nPP K=Q4CoterieDefinitionGiven a set of serversA coterie is a quorum system such thatCoteries are quorums of minimal size2121:, QQQQ P2},,{1 nPP K=Example Quorum SystemsSingletonMajority tolerates faulty serversWeighted Majority Every server is assigned votes}{21:P +==nQQ2nt <},,{1 nPP K=}}{{1P=}{2:P> =QqPqqqwwQ},,{1 nPP K=swsExample Quorum SystemsTree Quorumtolerates (*) faultyserversGrid A x grid of serversQuorum sizennode} leaf a to topfrompath :{ aPQ =},,{1 nPP K= nnt log<… …… …n)( nOn +21lognQnVoting and QuorumsWeighted Majority Every server is assigned votesMajority Voting Let V be the total number of votesDefine, r and w, the quorums required for read and write ops respectively2w > Vw + r > n}{2:P> =QqPqqqwwQ},,{1 nPP K=sws},,{1 nPP K=5Voting and QuorumsVote assignments and quorums are not equivalentQuorum systems are strictly more general than voting )2()2(22nOassigmentsvoteofNumberOquorumsofNumbercn==Measures on Quorum Systems Load Probability of accessing the busiest server in the bestcase (an optimal strategy of accessing the servers) Resilience Maximum number of faulty servers that the quorumsystem can tolerate Failure Probability Probability that at least one server of every quorum failsLoadAccess strategy : probability distribution on elements ofThe load induced by strategy on a serverThe load induced by onThe system load (or load) on a quorum system is=QwQP 1)(=QiQwwQPil : )()()(max)( ilLwPiw=)(min)(wwLL =wwwiComparison-TreePQSGridMajoritySingleton21 21n21)(<pne)(1nO)(1nO1nnln 110)21(>p)(L )(R)(pF1 )1log(2++nnn log21)(<pne6How do quorums work ? A quorum system implements a sharedread-write register in an asynchronouspoint-to-point networkLinearizability Each method call on an object should appear to• “take effect”• Instantaneously• Between invocation and response events Any such concurrent object is linearizable Two operations that• Non-Overlap: must be ordered in an order consistentwith their real-time precedence• Overlap: can be ordered either waySequential consistencyTwo operations that• Non-Overlap: must be ordered in that order(need not be their real-time precedence)• Overlap: can be ordered either wayLinearizability is strongertimeSequentially consistent but not linearizableq.enq(x)q.enq(x)q.enq(y)q.enq(y)q.deq(y)q.deq(y)time(6)q.enq(y)q.enq(y)q.deq(y)q.deq(y)q.enq(x)q.enq(x)7Exampletimeq.enq(x)q.enq(y) q.deq(x)q.deq(y)linearizableq.enq(x)q.enq(y) q.deq(x)q.deq(y)time(6)Serializability A transaction is a finite sequence ofmethod calls to a set of shared objects Serializable if• transactions appear to execute serially Strictly serializable if• order is compatible with real-time Used in databases Linearizability: single method, single objectStrict Serializability even strongerx.read(0)y.read(0)x.write(1)y.write(1)Non-serializableTransactions: A, B Shared Objects: x, ySemantics Safe:A read not concurrent with any write returns most recently written value Regular:Safe + a concurrent read (with a write) obtains either old or new value Atomic:Safe + reads and writes behave as if they occur in some definite orderwrite(0)read(1)write(1)read(0)8Semantics Safe:A read not concurrent with any write returns most recently written value Regular:Safe + a concurrent read (with a write) obtains either old or new value Atomic:Safe + reads and writes behave as if they occur in some definite orderwrite(1) write(2)read(2)Semantics Safe:A read not concurrent with any write returns most recently written value Regular:Safe + a concurrent read (with a write) obtains either old or new value Atomic:Safe + reads and writes behave as if they occur in some definite orderwrite(1) write(2)read(2)write(3)read(?)read(2) read(3)Semantics Safe:A read not concurrent with any write returns most recently written value Regular:Safe + a concurrent read (with a write) obtains either old or new value Atomic:Safe + reads and writes behave as if they occur in some definite orderwrite(1) write(2)read(2)read(?)read(2) read(3)read(?)read(2) read(3)read(3) read(2)write(3)Semantics Safe:A read not concurrent with any write returns most recently written value Regular:Safe + a concurrent read (with a write) obtains either old or new value Atomic:Safe + reads and writes behave as if they occur in some definite orderwrite(1) write(2)read(2)read(?)read(2) read(3)read(?)read(2) read(3)read(3) read(2)write(3)9Shared Read-Write Register Replicated Variable X Each server stores (v, ts)v – local copy of Xts – timestamp Operations• Write (V, _)• Read (X)xShared Read-Write Register Writer W: Write (V, )• Picks a quorum Q to get ts• > max {({ts} from Q) ,prev }• Sends (Write, V, ) operation tosome quorum Q’• Each server checks ts < ;setsX = V; ts =• W waits for |Q’| acks beforeterminating the writex Shared Read-Write Register Writer W: Write (V, )• Picks a quorum Q to get ts• > max {({ts} from Q)
View Full Document
Unlocking...