Arbitrary failures with message authenticationCrashArbitrary failures withmessage authenticationArbitrary (Byzantine) failuresSend OmissionGeneral OmissionReceive OmissionFail-stopProcess can send conflicting messages to different receiversMessages are signed with unforgeable signaturesValid messagesA valid message m has the following form:in round 1: . ( is signed by the sender)in round r > 1, if received by p from q: where = sender; are distinct from each other and from pmessage has not been tampered withp1, . . . , prp1pr= q< m : s >< m : p1: p2: . . . : pr>mAFMA: The IdeaA correct process p discard all non-valid messages it receivesIf a message is valid, it “extracts” the value from the messageit relays the message, with its own signature appendedAt round f + 1:if it extracted exactly one message, p delivers itotherwise, delivers SFAFMA: The Protocolsender s in round 0:1: extract msender in round 1:2: send < m:s > to all Process p in round k, 1 ≤ k ≤ f+13: if p extracted m from a valid message < m:p1: … :pk-1> in round k - 1 and p ≠ sender then4: send < m:p1: … :pk-1:p> to all5: receive round k messages from all processes6: for each valid round k message < m:p1: … :pk-1:pk> received by p7: if p has not previously extracted m then8: extract m9: if k = f+1 then10: if in the entire execution p has extracted exactly one m then11: deliver(m)12: else deliver(SF)13: haltTerminationIn round , every correct process delivers either or SF and then haltssender s in round 0:1: extract msender in round 1:2: send < m:s > to all Process p in round k, 1 ≤ k ≤ f+13: if p extracted m from a valid message <m:p1: … :pk-1> in round k - 1 and p ≠ sender then4: send <m:p1: … :pk-1:p> to all5: receive round k messages from all processes6: for each valid round k message < m:p1: … :pk-1:pk> received by p7: if p has not previously extracted m then8: extract m9: if k = f+1 then10: if in the entire execution p has extracted exactly one m then11: deliver(m)12: else deliver(SF)13: haltmf +1AgreementLemma If a correct process extracts m, then every correct process eventually extracts mProofLet r be the earliest round in which some correct process extracts m. Let that process be p.• if p is the sender, then in round 1 p sends a valid message to all. All correct processes extract message in round 1• otherwise, p has received in round r a message< m:p1:p2: … :pr >• Claim: p1, p2, …, pr are all faulty– true for p1 = s– Suppose pj, 1 ≤ j ≤ r, were correct• pj signed and relayed message in round j• pj extracted message in round j - 1CONTRADICTION• If r ≤ f, p will send a valid message < m:p1:p2: … :pr:p >in round r + 1 ≤ f + 1 and every correct process will extract it in round r + 1 ≤ f + 1 • If r = f + 1, by Claim above, p1, p2, …, pf+1 faulty– At most f faulty processes – CONTRADICTiONsender s in round 0:1: extract msender in round 1:2: send < m:s > to all Process p in round k, 1 ≤ k ≤ f+13: if p extracted m from a valid message <m:p1: … :pk-1> in round k - 1 and p ≠ sender then4: send <m:p1: … :pk-1:p> to all5: receive round k messages from all processes6: for each valid round k message < m:p1: … :pk-1:pk> received by p7: if p has not previously extracted m then8: extract m9: if k = f+1 then10: if in the entire execution p has extracted exactly one m then11: deliver(m)12: else deliver(SF)13: haltValidityFrom Agreement and the observation that the sender, if correct, delivers its own message.sender s in round 0:1: extract msender in round 1:2: send < m:s > to all Process p in round k, 1 ≤ k ≤ f+13: if p extracted m from a valid message <m:p1: … :pk-1> in round k - 1 and p ≠ sender then4: send <m:p1: … :pk-1:p> to all5: receive round k messages from all processes6: for each valid round k message < m:p1: … :pk-1:pk> received by p7: if p has not previously extracted m then8: extract m9: if k = f+1 then10: if in the entire execution p has extracted exactly one m then11: deliver(m)12: else deliver(SF)13: haltTRB for arbitrary failures CrashArbitrary failures withmessage authenticationArbitrary (Byzantine) failuresSend OmissionGeneral OmissionReceive OmissionFail-stopSrikanth, T.K., Toueg S.Simulating Authenticated Broadcasts to Derive Simple Fault-Tolerant AlgorithmsDistributed Computing 2 (2), 80-94AF: The IdeaIdentify the essential properties of message authentication that made AFMA workImplement these properties without using message authenticationAF: The ApproachIntroduce two primitivesbroadcast(p,m,i) (executed by p in round i)accept(p,m,i) (executed by q in round j ≥ i)Give axiomatic definitions of broadcast and acceptDerive an algorithm that solves TRB for AF using these primitivesShow an implementation of these primitives that does not use message authenticationProperties ofbroadcast and acceptCorrectness If a correct process executes broadcast(p,m,i) in round , then all correct processes will execute accept(p,m,i) in round Unforgeability If a correct process q executes accept(p,m,i) in round j ≥ i, and is correct, then did in fact execute broadcast(p,m,i) in round Relay If a correct process q executes accept(p,m,i) in round j ≥ i, then all correct processes will execute accept(p,m,i) by round j + 1ppiipiAF: The Protocol - 1sender s in round 0:0: extract msender s in round 1:1: broadcast (s,m,1)Process p in round k, 1 ≤ k ≤ f + 12: if p extracted m in round k - 1 and p ≠ sender then4: broadcast (p,m,k)5: if p has executed at least k accept(qi,m,ji) 1 ≤ i ≤ k in rounds 1 through k(where (i) qi distinct from each other and from p, (ii) one qi is s, and (iii) 1 ≤ ji ≤ k ) and p has not previously extracted m then6: extract m7: if k = f+1 then8: if in the entire execution p has extracted exactly one m then9: deliver(m)10: else deliver(SF)11: haltTerminationIn round , every correct process delivers either or SF and then haltssender s in round 0:0: extract msender s in round 1:1: broadcast (s,m,1)Process p in round k, 1 ≤ k ≤ f+12: if p extracted m in round k - 1 and p ≠ sender then4: broadcast (p,m,k)5: if p has executed at least k accept(qi,m,ji) 1 ≤ i ≤ k in rounds 1 through k(where (i) qi distinct from each other and from p, (ii) one qi is s, and (iii) 1 ≤ ji ≤ k ) and p has not previously extracted m then6: extract m7: if k = f+1 then8: if in the entire
View Full Document
Unlocking...