Consensus andReliable BroadcastBroadcastIf a process sends a message , then every process eventually delivers mmBroadcastIf a process sends a message , then every process eventually delivers p0p1p2p3mmBroadcastIf a process sends a message m, then every process eventually delivers mHow can we adapt the spec for an environment where processes can fail?p0p1p2p3Reliable Broadcast Validity If the sender is correct and broadcasts a message , then all correct processes eventually deliver Agreement If a correct process delivers a message , then all correct processes eventually deliver Integrity Every correct process delivers at most one message, and if it delivers , then some process must have broadcast mmmmmmTerminatingReliable Broadcast Termination Every correct process eventually delivers some messageValidity If the sender is correct and broadcasts a message , then all correct processes eventually deliver Agreement If a correct process delivers a message , then all correct processes eventually deliver Integrity Every correct process delivers at most one message, and if it delivers , then some process must have broadcast mmmmmmTerminatingReliable Broadcast Termination Every correct process eventually delivers some messageValidity If the sender is correct and broadcasts a message , then all correct processes eventually deliver Agreement If a correct process delivers a message , then all correct processes eventually deliver Integrity Every correct process delivers at most one message, and if it delivers ≠ SF, then some process must have broadcast mmmmmmConsensusTermination Every correct process eventually decides some valueValidity If all processes that propose a value propose , then all correct processes eventually decide Agreement If a correct process decides v, then all correct processes eventually decide Integrity Every correct process decides at most one value, and if it decides ≠ NU, then some process must have proposed vvvvvProperties of send(m) and receive(m)Benign failures:Validity If sends to , and , , and the link between them are correct, then eventually receives Uniform* Integrity For any message , receives at most once from , and only if . sent to * A property is uniform if it applies to both correct and faulty processesmmmmmppqqqqqppProperties of send(m) and receive(m)Arbitrary failures:Integrity For any message m, if p and q are correct then q receives m at most once from p, and only if p sent m to qQuestions, Questions…Are these problems solvable at all?Can they be solved independent of the failure model?Does solvability depend on the ratio between faulty and correct processes?Does solvability depend on assumptions about the reliability of the network?Are the problems solvable in both synchronous and asynchronous systems?If a solution exists, how expensive is it?PlanSynchronous SystemsConsensus for synchronous systems with crash failuresLower bound on the number of roundsEarly stopping protocols for Reliable BroadcastReliable Broadcast for arbitrary failures with message authenticationLower bound on the ratio of faulty processes for Consensus with arbitrary failuresReliable Broadcast for arbitrary failuresAsynchronous SystemsImpossibility of Consensus for crash failuresModelSynchronous Message PassingExecution is a sequence of roundsIn each round every process takes a stepsends messages to neighborsreceives messages sent in that roundchanges its stateNetwork is fully connected (an n-clique)No communication failuresA simple Consensus algorithmInitially V={vi}To execute propose(vi)1: send {vi} to all decide(x) occurs as follows:2: for all j, 0 ≤ j ≤ n-1, j ≠ i do3: receive Sj from pj 4: V:= V U Sj 5: decide min(V)Process pi:An executionp1p2p3p4p1p2p3p4v1v2v3v4An executionp1p2p3p4p1p2p3p4v1v2v3v4An executionp1p2p3p4p1p2p3p4v1v2v3v4v1v4Suppose at the end of round 1Can decide? v1= v3= v4p3An executionp1p2p3p4p1p2p3p4v1v2v3v4v1v4v2Suppose at the end of round 1Can decide? v1= v3= v4p3An executionp1p2p3p4p1p2p3p4v1v2v3v4v1v4Suppose at the end of round 1Can decide? v1= v3= v4p3v2An executionp1p2p3p4p1p2p3p4v1v2v3v4v1v4Suppose at the end of round 1Can decide? v1= v3= v4p3v2v1v1An executionp1p2p3p4p1p2p3p4v1v2v3v4v1v4Suppose at the end of round 1Can decide? v1= v3= v4p3v2v1v1v4An executionp1p2p3p4p1p2p3p4v1v2v3v4v1v4Suppose at the end of round 1Can decide? v1= v3= v4p3v2v1v1v4v3v3Echoing valuesA process that receives a proposal in round 1, relays it to others during round 2.Echoing valuesA process that receives a proposal in round 1, relays it to others during round 2.Suppose hasn’t heard from at the end of round 2. Can decide? p3p2p3Echoing valuesA process that receives a proposal in round 1, relays it to others during round 2.Suppose hasn’t heard from at the end of round 2. Can decide? p3p2p3p1p2p3p4p1p2p3p4p1p2p3p4round 1round 2What is going onA correct process has not received all proposals by the end of round . Can decide?Another process may have received the missing proposal at the end of round and be ready to relay it in round p∗p∗ii + 1iDangerous ChainsDangerous chain The last process in the chain is correct, all others are faultyround 1round 2roundsroundp∗p∗p∗p∗p0p1p2pi−1pi3...i − 1iLiving dangerouslyHow many rounds can a dangerous chain span? faulty processesat most nodes in the chainspans at most roundsIt is safe to decide by the end of round !ff +1ff +1The AlgorithmInitially V={vi}To execute propose(vi)round k, 1 ≤ k ≤ f+11: send {v in V : pi has not already sent v} to all 2: for all j, 0 ≤ j ≤ n-1, j ≠ i do3: receive Sj from pj 4: V:= V U Sj decide(x) occurs as follows:5: if k = f+1 then6: decide min(V)Code for process pi :Termination and IntegrityTerminationEvery correct process reaches round f + 1Decides on min(V) --- which is well defined Initially V={vi}To execute propose(vi)round k, 1 ≤ k ≤
View Full Document
Unlocking...