Transcript Traitorous Failures and Consensus

Traitorous Failures and
Consensus
Dennis Shasha (following Lynch,
Fischer, Merritt)
Problem Statement 1
• Three generals A, B, and C.
• At most one is a traitor.
• The traitor knows the protocol and the
inputs of the others.
• The generals must decide to attack or not to
attack (analogous to commit or abort).
Problem Statement 2
• Each day each general wakes up with an
inclination to attack or not to attack.
• The generals then talk to one another by
two way phone.
• So, A cannot overhear the conversation of B
with C and symmetrically.
Problem Statement 3
• If all generals wake up with an attack inclination,
the non-traitors should attack (liveness 1)
• If all generals wake up with a non-attack
inclination, the non-traitors should not attack
(liveness 2).
• If some wake up wanting to attack and others not,
then either both non-traitors should attack or both
should not attack (safety).
What Makes this Hard
• If all generals could get together in a single
room, they could simply vote.
• If two vote to attack then at least one nontraitor wanted to attack, so attacking
accords with the rule.
• If two vote not to attack then at least one
non-traitor didn’t want to attack, so that’s
ok.
Communication Is Only Two
Way
• If A is a traitor, then A could say one thing
to B and another thing to C.
• B and C could later communicate, but they
wouldn’t know whether the inconsistency
came from A or from one another.
Scenario 1
• All generals have an inclination to attack.
• However C is a traitor. What each general
says is in parentheses next to it.
• C(no) (yes)A(yes) (yes)B(yes) (yes)C
• A and B should both say attack.
Scenario 2
• A has an inclination to attack. C does not
and B is the traitor.
• C(no) (yes)A(yes) (yes)B(no) (no)C
• To A, the situation is as it was for Scenario
1, so A attacks. C, in order to preserve
safety, must also attack.
Scenario 3
• Nobody has an inclination to attack. A is the
traitor
• C(no) (yes)A(no) (no)B(no) (no)C
• To C, the situation is as it was in scenario 2,
so C attacks. But this violates our second
liveness condition.
Summary
• Even if you have only one traitor, two way
communication cannot guarantee a correct
decision among three generals.
• Three way communication could have done
so and so could signed communication,
because then no general could have told
inconsistent stories.
Postscript
• “If I were two-faced, would I be wearing
this one?” Abraham Lincoln