Failures and ConsensusCoordinationOverviewConsensusProperties for Correct ConsensusVariant I: Consensus (C)Variant II: Command Consensus (BG)Variant III: Interactive Consistency (IC)Equivalence of Consensus VariantsFour Dimensions of Failure ModelsAssumptionsConsensus: synchronous with no failuresConsensus: synchronous fail-stopLamport’s 1982 Result, Generalized by PeaseImpossibility with three byzantine generalsSolution with four byzantine generalsSummary: Byzantine FailuresFischer-Lynch-Patterson (1985)Consensus in Practice IConsensus in Practice IIRecovery for Fault MaskingExample: Session VerifierFailure DetectorsFailure Detectors in Real SystemsA network partitionGroup Membership ServicesSlide 27Group Membership ServiceChandra/Toueg Failure DetectorsSample propertiesSlide 31A sampling of failure detectorsPerfect Detector?Example of a failure detectorW: Weakest failure detectorBuilding systems with WFailures and ConsensusFailures and ConsensusCoordinationCoordinationIf the solution to availability and scalability is to decentralize and replicate functions and data, how do we coordinate the nodes?•data consistency•update propagation•mutual exclusion•consistent global states•group membership•group communication•event ordering•distributed consensus•quorum consensusOverviewOverview•The consensus problem and its variants•Failure models•Consensus in synchronous model with no failures•Consensus in synchronous model with fail-stop•The trouble with byzantine failures•Impossibility of consensus with too many byzantine failures•Consensus in synchronous with a few byzantine failures•Impossibility of consensus in asynchronous with failures•Consensus in practice anyway•Recovery and failure detectorsConsensusConsensusUnreliable multicastStep 1Propose.P1 P2 P3 v1 v3 v2 Consensus algorithmStep 2Decide.P1 P2 P3 d1 d3 d2 Generalizes to N nodes/processes.Properties for Correct ConsensusProperties for Correct ConsensusTermination: All correct processes eventually decide.Agreement: All correct processes select the same di.Or…(stronger) all processes that do decide select the same di, even if they later fail.Integrity: All deciding processes select the “right” value.•As specified for the variants of the consensus problem.Variant I: Consensus (C)Variant I: Consensus (C)Pi selects di from {v0, …, vN-1}.All Pi select di as the same vk .If all Pi propose the same v, then di = v, else di is arbitrary.di = vkVariant II: Command Consensus (BG)Variant II: Command Consensus (BG)Pi selects di = vleader proposed by designated leader node Pleader if the leader is correct, else the selected value is arbitrary.As used in the Byzantine generals problem. Also called attacking armies.di = vleadervleaderleader orcommandersubordinate orlieutenantVariant III: Interactive Consistency (IC)Variant III: Interactive Consistency (IC)Pi selects di = [v0 , …, vN-1] vector reflecting the values proposed by all correct participants.di = [v0 , …, vN-1]Equivalence of Consensus VariantsEquivalence of Consensus VariantsIf any of the consensus variants has a solution, then all of them have a solution.Proof is by reduction.•IC from BG. Run BG N times, one with each Pi as leader.•C from IC. Run IC, then select from the vector.•BG from C.Step 1: leader proposes to all subordinates.Step 2: subordinates run C to agree on the proposed value.•IC from C? BG from IC? Etc.Four Dimensions of Failure ModelsFour Dimensions of Failure ModelsReliable vs. unreliable networkReliable: all messages are eventually delivered exactly once.Synchronous vs. asynchronous communicationSynchronous: message delays (and process delays) are bounded, enabling communication in synchronous rounds.Byzantine vs. fail-stopFail-stop: faulty nodes stop and do not send.Byzantine: faulty nodes may send arbitrary messages.Authenticated vs. unauthenticatedAuthenticated: the source and content of every message can be verified, even if a Byzantine failure occurs.AssumptionsAssumptionsFor now we assume:•Nodes/processes communicate only by messages.•The network may be synchronous or asynchronous.•The network channels are reliable.Is this realistic?There are three kinds of node/process failures:•Fail-stop•Authenticated Byzantine (“signed messages”)•Byzantine (“unsigned”)Consensus: synchronous with no failuresConsensus: synchronous with no failuresThe solution is trivial in one round of proposal messages.Intuition: all processes receive the same values, the values sent by the other processes.Step 1. Propose.Step 2. At end of round, each Pi decides from received values.•Consensus: apply any deterministic function to {v0,…, vN-1}.•Command consensus: if vleader was received, select it, else apply any deterministic function to {v0,…, vN-1}.•Interactive consistency: construct a vector from all received values.Consensus: synchronous fail-stopConsensus: synchronous fail-stopF+1 rounds of exchanges can reach consensus for N processes with up to F processes failing.In each round, each node says everything that it knows that it hasn’t already said in previous rounds.At most N2 values are sent.Intuition: suppose Pi learns a value v from Pj during a round.•Other correct processes also learned v from Pj during that round, unless Pj failed during the round.•Other correct processes will learn it from Pi in the next round, unless Pi also fails during that round.•Adversary must fail one process in each round, after sending its value to one other process…so F+1 rounds are sufficient if at most F failures occur.Lamport’s 1982 Result, Generalized by PeaseLamport’s 1982 Result, Generalized by PeaseThe Lamport/Pease result shows that consensus is impossible:•with byzantine failures,•if one-third or more processes fail (N ≤ 3F),Lamport shows it for 3 processes, but Pease generalizes to N.•even with synchronous communication.Intuition: a node presented with inconsistent information cannot determine which process is faulty.The good news: consensus can be reached if N > 3F, no matter what kinds of node failures occur.Impossibility with three byzantine generalsImpossibility with three byzantine generalsp1 (Commander)p2p31:v1:v2:1:v3:1:up1 (Commander)p2p31:x1:w2:1:w3:1:xFaulty processes are shown shaded[Lamport82]Intuition: subordinates cannot distinguish these cases.Each must select the commander’s value in the first case, but this means they cannot agree in the second