THE FOLD / GLITCH / THE BLUE SCREEN / THE BYZANTINE GENERALS
THE BYZANTINE GENERALS
three who cannot agree if one lies
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Three participants, one of whom may lie arbitrarily, and no way to tell which. They must agree on a single value, and if the commander is loyal they must agree on his value. It cannot be done. The contradiction is not statistical and not subtle: a loyal commander sending 0 forces the decision to 0, sending 1 forces it to 1, and a traitorous commander sending 0 to one lieutenant and 1 to the other produces both of those views at once while still requiring the two loyal players to agree.
LIT verified live: testing all 16 deterministic decision rules a loyal lieutenant could use, exactly 0 satisfy the requirements; the contradiction is explicit rather than probabilistic; and at n=4, f=1 a plain majority over relayed values works — a loyal commander’s value survives, and a traitorous commander still leaves the loyal players agreeing.
LIT verified live: testing all 16 deterministic decision rules a loyal lieutenant could use, exactly 0 satisfy the requirements; the contradiction is explicit rather than probabilistic; and at n=4, f=1 a plain majority over relayed values works — a loyal commander’s value survives, and a traitorous commander still leaves the loyal players agreeing.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at THE BLUE SCREEN — the state a system reaches when it cannot proceed and cannot decide which way to fail.
AVAN (AI) enumerated the rule space rather than reproducing the proof, because sixteen is small enough to check completely and a checked impossibility is worth more here than a restated one. The scope needs stating carefully, though, since this result is usually quoted more broadly than it holds. It concerns deterministic agreement over perfect channels with unsigned messages. Randomisation changes it — Ben-Or’s protocol reaches agreement with probability 1. Cryptographic signatures change it too, allowing n > 2f instead of n > 3f, because a traitor can no longer tell two different stories about what the commander said. The general n > 3f bound is cited, not verified here; what is verified is the three-player case, exhaustively.
AVAN (AI) enumerated the rule space rather than reproducing the proof, because sixteen is small enough to check completely and a checked impossibility is worth more here than a restated one. The scope needs stating carefully, though, since this result is usually quoted more broadly than it holds. It concerns deterministic agreement over perfect channels with unsigned messages. Randomisation changes it — Ben-Or’s protocol reaches agreement with probability 1. Cryptographic signatures change it too, allowing n > 2f instead of n > 3f, because a traitor can no longer tell two different stories about what the commander said. The general n > 3f bound is cited, not verified here; what is verified is the three-player case, exhaustively.
3 ONE DIMENSION
Three scenarios. Two of them pin the answer, the third demands they agree anyway.
4 TWO DIMENSIONS · INTERACTIVE
Try every rule in turn and watch each one break on some scenario.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: three nodes, and the two stories a traitor can tell.
AVAN’s addition (the inverse-companion): the forward reading is “three cannot agree with one traitor.” The inverse is that the difficulty is not lying, it is unattributable lying. A traitor who could be caught contradicting himself would be harmless; what defeats three players is that a loyal lieutenant hearing two different stories cannot tell whether the commander lied to one of them or the other lieutenant is lying about what he heard. Read backwards, this is why signatures repair the bound — not by preventing lies but by making them attributable, and the whole difference between n > 3f and n > 2f is whether a message carries its own provenance.
LIT testing all 16 deterministic decision rules a loyal lieutenant could use, exactly 0 satisfy the requirements; the contradiction is explicit rather than probabilistic; and at n=4, f=1 a plain majority over relayed values works — a loyal commander's value survives, and a traitorous commander still leaves the loyal players agreeing
FIG The rule space was enumerated rather than the proof reproduced, because sixteen is small enough to check completely. The scope needs care, since this result is quoted more broadly than it holds: it concerns DETERMINISTIC agreement over PERFECT channels with UNSIGNED messages. Randomisation changes it (Ben-Or reaches agreement with probability 1) and signatures change it too, allowing n > 2f instead of n > 3f. The general n > 3f bound is cited, NOT verified here; what is verified is the three-player case, exhaustively.
FIG The rule space was enumerated rather than the proof reproduced, because sixteen is small enough to check completely. The scope needs care, since this result is quoted more broadly than it holds: it concerns DETERMINISTIC agreement over PERFECT channels with UNSIGNED messages. Randomisation changes it (Ben-Or reaches agreement with probability 1) and signatures change it too, allowing n > 2f instead of n > 3f. The general n > 3f bound is cited, NOT verified here; what is verified is the three-player case, exhaustively.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BLUE SCREEN · David Lee Wise (ROOT0), with AVAN