Unreliable Failure Detectorsfor Reliable Distributed SystemsA different approachAugment the asynchronous model with an unreliable failure detector for crash failuresDefine failure detectors in terms of abstract properties, not specific implementationsIdentify classes of failure detectors that allow to solve ConsensusThe ModelGeneralasynchronous systemprocesses fail by crashinga failed process does not recoverFailure Detectorsoutputs set of processes that it currently suspects to have crashedthe set may be different for different processesCompletenessStrong Completeness Eventually every process that crashes is permanently suspected by every correct processWeak Completeness Eventually every process that crashes is permanently suspected by some correct processAccuracyStrong Accuracy No correct process is ever suspectedWeak Accuracy Some correct process is never suspectedAccuracyStrong Accuracy No correct process is ever suspectedWeak Accuracy Some correct process is never suspectedEventual Strong Accuracy There is a time after which no correct process is ever suspectedEventual Weak Accuracy There is a time after which some correct process is never suspectedFailure detectorsCompletenessAccuracyStrongWeakEventual strongEventual weakStrongPerfect .Strong .WeakQuasi.......Weak .♦P♦Q♦S♦WWSPQReducibility transforms failure detector . into failure detector If we can transform into then we say that is stronger than and that is reducible to If and then we say that and are equivalent: Algorithm A uses DTD→D!TD→D!DD!D ≥ D!D!≥ DDD!DD!D!DDD!D ≡ D!D!Simplify, Simplify!All weakly complete failure detectors are reducible to strongly complete failure detectorsP ≥ Q, S ≥ W, ♦P ≥ ♦Q, ♦S ≥ ♦WSimplify, Simplify!All weakly complete failure detectors are reducible to strongly complete failure detectorsAll strongly complete failure detectors are reducible to weakly complete failure detectors (!)Weakly and strongly complete failure detectors are equivalent!P ≥ Q, S ≥ W, ♦P ≥ ♦Q, ♦S ≥ ♦WQ≥ P, W ≥ S, ♦Q≥ ♦P, ♦W ≥ ♦SFrom Weak Completenessto Strong CompletenessEvery process p executes the following: := 0cobegin|| Task 1: repeat forever{ queries its local failure detector module } := send ( ) to all|| Task 2: when receive( ) from some := ( ) -coend DpDpoutputpoutputpoutputp∪ suspectspsuspectspq, suspectsqp, suspectspq{q}pThe TheoremsTheorem 1 In an asynchronous system with , consensus can be solved as long as f ≤ n−1WThe TheoremsTheorem 1 In an asynchronous system with , consensus can be solved as long as Theorem 2 There is no -resilient consensus protocol using for f ≤ n−1Wf ≥ n/2♦PfThe TheoremsTheorem 1 In an asynchronous system with , consensus can be solved as long as Theorem 2 There is no -resilient consensus protocol using for Theorem 3 In asynchronous systems in which processes can use , consensus can be solved as long as f ≤ n−1W♦Wf <n/2f ≥ n/2♦PfThe TheoremsTheorem 1 In an asynchronous system with , consensus can be solved as long as Theorem 2 There is no -resilient consensus protocol using for Theorem 3 In asynchronous systems in which processes can use , consensus can be solved as long asTheorem 4 A failure detector can solve consensus only if it satisfies weak completeness and eventual weak accuracy–i.e. is the weakest failure detector that can solve consensus. f ≤ n−1W♦Wf <n/2f ≥ n/2♦Pf♦WSolving consensus using . : Strong Completeness, Weak Accuracyat least some correct process is never suspectedEach process has its own failure detector Input values are chosen from the set {0,1}ScpSNotationWe introduce the operators ⊕, , ⊗ They operate element-wise on vectors whose entries have values from the set {0, 1, ⊥}v ⊥ = v ⊥ v = vv v = ⊥ ⊥ ⊥ = ⊥v ⊕ ⊥ = v ⊥ ⊕ v = vv ⊕ v = v ⊥ ⊕ ⊥ = ⊥v ⊗ ⊥ = ⊥ ⊥ ⊗ v = ⊥ v ⊗ v = v ⊥ ⊗ ⊥ = ⊥Given two vectors A and B, we write A ≤ B if A[i] ≠ ⊥ implies B[i] ≠ ⊥Solving Consensususing any . 1: := {p’s estimate of the proposed values} 2: := 3: {phase 1} {asynchronous rounds , } 4: for := 1 to 5: send to all 6: wait until [: received or ] {query the failure detector} 7: := 8: := 9: := {value is only echoed the first time it is seen} 10: {phase 2}11: send to all12: wait until [: received or ]13: := {computes the “intersection”, including }14: {phase 3}15: decide on leftmost non- coordinate of (rp, ∆p, p)Vp(⊥, . . . , ⊥, vp, ⊥, . . . , ⊥)∆p(⊥, . . . , ⊥, vp, ⊥, . . . , ⊥)rp∀q(rp, ∆q, q)q ∈ DpOpVpVp⊕ (⊕q received∆q)Vp∆p(rp, Vp, p)(rp, Vq, q)q ∈ Dp∀q⊗q receivedVqVpVpVp1 ≤ rp≤ n − 1rpVp! Opn− 1D ∈ SA useful LemmaLemma 1 After phase 1 is complete, . for all processes that complete phase 1 1: Vp := (⊥, …, ⊥, vp, ⊥, …, ⊥){p’s estimate of the proposed values} 2: Δp := (⊥, …, ⊥, vp, ⊥, …, ⊥) 3: {phase 1}{asynchronous rounds rp, 1≤ rp ≤ n – 1} 4: for rp := 1 to n-1 5: send (rp, Δp ,p) to all 6: wait until [∀q: received (rp, Δq ,q) or q ∈ Dp] 7: Op := Vp 8: Vp := Vp ⊕ (⊕q received Δq) 9: Δp := Vp Op {value is only echoed first time it is seen} 10: {phase 2}11: send (rp, Vp ,p) to all12: wait until [∀q: received (rp, Vq ,q) or q ∈ Dp]13: Vp := ⊗q received Vq{computes the “intersection”, including Vp}14: {phase 3}15: decide on leftmost non- ⊥ coordinate of Vp Vc≤ VppA useful LemmaLemma 1 After phase 1 is complete, . for all processes that complete phase 1Proof We show thatLet be the first round when sees . will send to all with in round By weak accuracy, all correct processes receive by next round . has been forwarded times: every other process has seen 1: Vp := (⊥, …, ⊥, vp, ⊥, …, ⊥){p’s estimate of the proposed values} 2: Δp := (⊥, …, ⊥, vp, ⊥, …, ⊥) 3: {phase 1}{asynchronous rounds rp, 1≤ rp ≤ n – 1} 4: for rp := 1 to n-1 5: send (rp, Δp ,p) to all 6: wait until [∀q: received (rp, Δq ,q) or q ∈ Dp] 7: Op := Vp 8: Vp := Vp ⊕ (⊕q received Δq) 9: Δp :=
View Full Document
Unlocking...