TurpinCoan BenOr
More Fault Tolerant Consensus
Radu Nicolescu Department of Computer Science University of Auckland
21 Oct 2020
1/15
TurpinCoan BenOr
1 TurpinCoan Sync Multi
2 BenOr Async Stop
2/15
TurpinCoan BenOr
TurpinCoan Sync Multi
• General agreement, over arbitrary finite set V , |V | ≥ 2 • TurpinCoan: two extra rounds + binary Byz
4/15
TurpinCoan BenOr
TurpinCoan Init aka Round 0 (Process #i)
• Initial choice: x ∈ V
• determined by other means, or • received from outside
• Proposal: y ∈ V ∪ ⊥ = ⊥ • Candidate: z ∈ V ∪ ⊥ = ⊥ • Vote: vˆ ∈ {0, 1} = 0
5/15
TurpinCoan BenOr
TurpinCoan Round 1 (Process #i)
• Send x to all processes
• Let W ⊆ V ∪ ⊥ = multiset of all received messages • |W | = N : sync, ⊥
• If ∃v ∈ V , |W |v ≥ N − F = 2F + 1, then y = v
• Else, keep y =⊥
• y∈V∪⊥isourproposal
• Note: all non-faulty processes select the same y ∈ V ∪ ⊥ • aaab⇒y=a,aaac⇒y=a
• aaab⇒y=a,aacb⇒y=⊥
6/15
TurpinCoan BenOr
TurpinCoan Round 2 (Process #i)
• Send y ∈ V ∪ ⊥ to all processes
• Let W ⊆ V ∪ ⊥ = multiset of all received messages
• |W | = N : sync, ⊥
• If ∃v ∈ V , |W |v ≥ N − F = 2F + 1, then z = v , vˆ = 1 • We vote for candidate z ∈ V
• Else if ∃v ∈ V,argmaxv |W|v, arbitrary tie break, then z = v (vˆ = 0)
• We do NOT vote for candidate z ∈ V, but this may be the final decision
• Else i.e. |W | ∩ V = ∅. (z =⊥, vˆ = 0) • No candidate, no vote
7/15
TurpinCoan BenOr
TurpinCoan Round 3, … (Process #i)
• Binary Byz agreement on vˆ ∈ {0, 1}, for the candidate z∈V∪⊥
• If this Byz decision is 1 and z ∈ V (i.e. z ̸=⊥), then final decision z
• Else, final decision v0 ∈ V
8/15
TurpinCoan BenOr
TurpinCoan Other Agreement Examples
The three loyal processes start with aab, a, b ∈ V , the last process is faulty
• Variant agreement: z = a ∈ V
• aaba⇒y=a,aa⊥a⇒z=a,vˆ=1,110 ⇒1 • aaba⇒y=a,aa⊥a⇒z=a,vˆ=1,110 ⇒1 • aabb⇒y=⊥,aa⊥b⇒z=a,vˆ=0,110 ⇒1
• Variant agreement: z = v0 ∈ V
• aaba⇒y=a,aa⊥a⇒z=a,vˆ=1,1100⇒0 • aaba⇒y=a,aa⊥a⇒z=a,vˆ=1,1100⇒0 • aabb⇒y=⊥,aa⊥b⇒z=a,vˆ=0,1100⇒0
9/15
TurpinCoan BenOr
TurpinCoan Other Agreement Examples
The three loyal processes start with abc, a, b, c ∈ V , the last process is faulty
• Agreement: z = v0 ∈ V
• abca⇒y=⊥,⊥⊥⊥d⇒z=d,vˆ=0,000 ⇒0 • abca⇒y=⊥,⊥⊥⊥e⇒z=e,vˆ=0,000 ⇒0 • abcb⇒y=⊥,⊥⊥⊥e⇒z=f,vˆ=0,000 ⇒0
• Agreement may be impossible with just one extra (second) round
• aaba···⇒z=a,vˆ=1,1101⇒1 • aaba···⇒z=a,vˆ=1,1101⇒1 • aabb···⇒z=b,vˆ=0,1101⇒1
10/15
TurpinCoan BenOr
BenOr Async Stop
• FLP: no agreement in the async model, even if one single stopping failure
• Still, this is a fundamental problem that needs solutions!
• Way around: stronger model, and weaker termination
• Stronger model: processes use randomisation
• Weaker termination: eventual termination with probability=1
12/15
TurpinCoan BenOr
BenOr Init aka Round 0 (Process #i)
• Initial choice: x ∈ {0, 1}
• determined by other means, or • received from outside
• Proposal: y ∈ {0, 1, ⊥} =⊥ • Step: s ≥ 0 = 0, unbounded • Each step has two rounds
13/15
TurpinCoan BenOr
BenOr Step s, Round 1 (Process #i)
• Send (I,s,x) to all processes
• LetM=multisetoffirstN−F=2F+1receivedmessages
(I,s,∗)
• Ifallm∈Mhavesamevaluev∈{0,1},theny=v • Else, y =⊥
14/15
TurpinCoan BenOr
BenOr Step s, Round 2 (Process #i)
• Send (II,s,y) to all processes
• LetM=multisetoffirstN−F=2F+1receivedmessages
(II,s,∗)
• Ifallm∈Mhavesamevaluev∈{0,1},thenx=v,decide
v (if not already), and continue
• IfatleastN−2F=F+1m∈Mhavesamevalue
v ∈ {0,1}, then x = v, but do not decide
• Else i.e. x = random ∈ {0, 1}.
15/15