1CS395T: Design/Implementation of Trusted ServersByzantine Quorum SystemsbyAnurag AgarwalCS395T: Design/Implementation of Trusted ServersCourtesy : FromByzantine Agreement toPractical survivabilityD. MalkhiCS395T: Design/Implementation of Trusted ServersSystem Model Universe U of servers |U| = n Quorum system Byzantine faulty servers Modeled as fail-prone system Some contains all the faulty servers Initially clients assumed to be correct Point to point authenticated and reliableasynchronous channel[MR98]CS395T: Design/Implementation of Trusted ServersAccess Protocol Each server stores value v and timestamp T Client c chooses timestamps from set Tc For clients c and c’, Tc and Tc’ don’t intersect Write (v) Query servers to get a set A of timestamps forsome quorum Q Choose a timestamp t in Tc greater than highest inA and greater than any of its previous timestamps Send update <v,t> to servers untilacknowledgement from some quorum Q’ isreceived2CS395T: Design/Implementation of Trusted ServersAccess Protocol Read() Query servers to obtain value/timestamp pairs Afor some quorum Q Applies a deterministic function “Result(A)” toobtain the result of read operation “Result” function Depends on the type of quorum systems Chosen to guarantee safe semanticsCS395T: Design/Implementation of Trusted ServersMasking Quorum Systems A quorum system is a masking quorum system fora fail prone system if the following properties aresatisfied : M-consistency M-availabilityCS395T: Design/Implementation of Trusted ServersMasking Quorum Systems Read : “Result()” function Client receives the responses Computes the set Chooses the pair in with highest timestampCS395T: Design/Implementation of Trusted Serversf – masking Quorum System M-consistency M-availability Quorum system exists iff3CS395T: Design/Implementation of Trusted ServersGrid Quorum , Arrange the universe in a k x k grid A masking quorum system ( Cj – columns, Ri – rows)n = 5 x 5, f =1CS395T: Design/Implementation of Trusted ServersDissemination QuorumSystems Quorums for self verifying data Only clients can create the data Clients can detect attempted changes by a faultyserver D-consistency D-availabilityCS395T: Design/Implementation of Trusted ServersDissemination QuorumSystems Read : “Result()” function Client receives the responses Computes the set of pairs which are verifiable Chooses the pair in with highesttimestampCS395T: Design/Implementation of Trusted Serversf – dissemination QuorumSystem D-consistency D-availability Quorum system exists iff4CS395T: Design/Implementation of Trusted ServersGrid Quorum , Arrange the universe in a k x k grid A masking quorum system ( Cj – columns, Ri – rows)n = 5 x 5, f =1CS395T: Design/Implementation of Trusted ServersOpaque Masking QuorumSystems Masking quorums require the client to knowthe fail prone system Problems Read protocol becomes complicated Revealing possible failure scenarios for which thesystem is designed Design quorums such that clients don’t needto knowCS395T: Design/Implementation of Trusted ServersOpaque Masking QuorumSystems - Properties O-Consistency1: O-Consistency2: O-availabilityCS395T: Design/Implementation of Trusted ServersOpaque Masking QuorumSystems Read : “Result()” function Client receives the responses Computes the set of pairs which appear mostoften Chooses the pair in with highesttimestamp f-opaque quorum system Exists iff5CS395T: Design/Implementation of Trusted ServersByzantine Clients Problems Send different updates to different servers Leaves system inconsistent May write data that corrupts the state Impossible for servers to avoid Protocol ensures that clients don’t leavesystem in an inconsistent state Works for single writer, multiple reader Masking Quorum SystemsCS395T: Design/Implementation of Trusted ServersClient Write protocol1) Choose a timestamp t in Tc greater than anyvalue it has chosen before2) Choose a quorum Q and send an updatemessage <update,Q,v,t> to each server in Q3) If it does not receive ack from all the serversin Q within some time, repeat the steps 2 and 3CS395T: Design/Implementation of Trusted ServersServer Write Protocol Two sets to remember such that Protocol If a server receives a fresh <update,Q,v,t>, thensend <echo,Q,v,t> to each member of Q If a server receives identical echo messages<echo,Q,v,t> from every server in Q, then it sendsa <ready,Q,v,t> to each member in QCS395T: Design/Implementation of Trusted ServersServer Write Protocol If a server receives identical ready messages<ready,Q,v,t> from a set B+, then it sends a<ready,Q,v,t> to each member in Q if it has notdone so already. If a server receives identical ready messages<ready,Q,v,t> from a set Q- of servers, then(i) if t is greater than its current timestamp, update v and t (ii) send an ack to c even if the value was not updatedAt this point the server is said to have delivered <v,t>6CS395T: Design/Implementation of Trusted ServersProof of Correctness Duration of write operation Starts when first correct server receives updatemessage Ends when all correct servers in a quorum havedelivered the update Need to show Safe semantics Also prove Liveness CompletenessCS395T: Design/Implementation of Trusted ServersProof of CorrectnessLemma 1 : A correct server delivers <v,t> only if some correctserver previously received <update,Q,v,t>Proof :(1) To deliver <v,t>, a correct server must have received ready message from acorrect server(2) First ready message from a correct server when it has received echo from allthe servers in Q(3) Correct member sends <echo,Q,v,t> only if it receives <update,Q,v,t>Lemma 2 (Agreement): If a correct server deilvers <v,t> and acorrect server delivers <v’,t>, then v = v’Proof : (1) One quorum Q1 must have sent <echo,Q1,v,t> (2) Another quorum Q2 must have sent <echo,Q2,v’,t> (3) Q1 and Q2 have at least one correct server in common, so v must beidentical to v’CS395T: Design/Implementation of Trusted ServersProof of CorrectnessLemma 3(Safe Semantics) : A correct process’s read operationthat is concurrent with no write operations returns the valuewritten
View Full Document
Unlocking...