Fault tolerance · 1982 · Leslie Lamport, Robert Shostak & Marshall Pease
The Byzantine Generals Problem
Model contradictory, adversarial failure explicitly and derive the conditions under which correct processes can still agree.
How to read the original
- Read Introduction and separate agreement from the loyal-commander requirement.
- Read A Solution with Oral Messages, including the stated communication assumptions.
- Read A Solution with Signed Messages and identify exactly which forgery capability changes.
Failure can send different stories
The paper treats a faulty participant as capable of contradictory behavior, not merely silence. Its agreement requirement must coexist with a validity requirement: when the commander is loyal, loyal lieutenants use that commander’s value. For oral messages, tolerating at most f traitors requires more than 3f participants under the paper’s communication model. Signatures change the information available to recipients, but do not remove the need to specify delivery and timing assumptions.
Original reconstruction: four participants, one faulty commander
Use commander C and lieutenants A, B, and D, with at most one faulty participant. Let possible orders be 1 for advance and 0 for hold. Assume messages between loyal participants are delivered correctly, the immediate sender is identifiable, and a missing expected message can be detected under the protocol’s round assumptions. These are stronger premises than arbitrary asynchronous Internet delivery.
Suppose C is faulty. It sends 1 to A, 0 to B, and 1 to D. Each loyal lieutenant relays the value it received to the other lieutenants. A assembles the vector [1,0,1], using its own direct value in A’s position and the relayed values for B and D. B and D assemble the same vector. Their deterministic majority rule yields 1, so they agree even though the commander equivocated.
Agreement does not mean the chosen value reflects C’s authentic intention. A faulty C has no trustworthy single intention in this execution. Nor does the algorithm prove that advancing is strategically wise. The protocol guarantees a precisely stated relationship among decisions; it cannot create correctness of external information that the model does not supply.
Now make C loyal and B faulty. C sends 1 to everyone. A and D relay 1 faithfully; B may relay 0, omit messages, or tell each recipient a different story. Each loyal lieutenant still has two entries supporting 1 and at most one corrupted entry. The majority returns the loyal commander’s value. This second trace checks validity, which the first trace could not test because its commander was faulty.
Why forwarding alone is insufficient with three
With only a commander and two lieutenants, a loyal recipient can hear one direct value and one conflicting report without knowing which source is faulty. One possible world has a lying commander; another has a loyal commander and lying fellow lieutenant. The recipient’s local evidence can be the same while the required decision differs. A correct lower-bound argument builds such indistinguishable executions rather than asserting that disagreement merely seems likely.
Authentication changes evidence, not reality
If a commander’s signed order can be forwarded and verified without being forged, a lieutenant can show what was actually signed rather than ask others to trust its paraphrase. A malicious signer can still sign conflicting orders. The signed-message algorithm must therefore specify how recipients collect authenticated statements and choose deterministically from the resulting set.
For a lab, enumerate who is faulty, what every link delivers, and the final decisions. Test agreement and validity as separate predicates. Include omissions under the specified round model and verify the default rule. Do not translate the oral-message bound into a universal claim about every blockchain or network: membership, authentication, synchrony, fault type, and the required decision property all influence the applicable theorem. The paper teaches how assumptions support a guarantee, not a magic participant count.
Reconstruction exercise
With loyal commander C sending 0 and one faulty lieutenant B, let B tell A that it received 1 and tell D that it received 0. Write the three-value decision vector seen by each loyal lieutenant in the four-participant example and decide the result. Then explain why a two-participant agreement algorithm cannot be justified merely by saying that cryptographic signatures are strong.
Worked solution
A’s vector, ordered by A, B, D, is [0,1,0]. D’s vector is [0,0,0]. The vectors need not be identical when a lieutenant is faulty, but both majorities are zero. Thus the loyal lieutenants agree and preserve the loyal commander’s order. The faulty participant’s own decision is unconstrained. Strong signatures establish whether a particular key authenticated a statement, assuming sound keys and verification. They do not guarantee message delivery, detect an indefinitely delayed message in a fully asynchronous setting, or select a decision rule when a signer authenticates conflicting statements. Any claim about a two-participant protocol must specify its agreement and validity properties, fault bound, network timing, and termination conditions. Authentication changes a key premise; it does not replace the rest of the protocol or its proof.
Test the limits and transfer the idea
1. Finite model and proof · allow 60 minutes
Exhaust a small oral-message model
Model OM(1) with commander C and lieutenants A, B, D. Values are 0, 1, or an omitted message, interpreted as default 0. Loyal lieutenants relay their received value faithfully. Each loyal lieutenant takes the majority of three entries: its own direct value and the values relayed by the other two lieutenants.
Enumerate: two all-loyal commander values; all 27 triples a faulty commander can send; and, for each of three possible faulty lieutenants and each loyal commander value, all nine pairs that lieutenant can relay to the other loyal lieutenants. Check agreement among loyal lieutenants and, when C is loyal, validity. Explain why exhaustive testing here does not prove the general Byzantine agreement theorem.
Get a starting hint
Keep the faulty lieutenant's decision out of agreement checks. The two fault cases have different proofs: a faulty commander yields a common vector; a faulty lieutenant leaves two loyal entries.
Compare your reasoning with the worked solution
The enumeration contains 2 + 27 + 3 × 2 × 9 = 83 scenarios. When C is faulty, all three lieutenants are loyal. Each lieutenant's decision vector consists of the same three values received directly by A, B, and D, although the local entry order may differ. Thus every majority is identical. The resulting value need not equal any supposed intention of the faulty commander.
When C is loyal and one lieutenant is faulty, each loyal lieutenant has the commander's value as its direct entry and receives that same value from the other loyal lieutenant. These two entries outvote whatever the faulty lieutenant sends. This proves both validity and agreement for this case. In the all-loyal case every entry is the commander's value.
An implementation can normalize omission to 0 at message receipt and use sum(entries) >= 2 for majority. It should assert that the set of loyal decisions has size one, then separately assert equality to the loyal commander's order when applicable. Normalizing omissions creates duplicate effective scenarios, but retaining all 83 raw scenarios checks the omission handling as specified.
This is an exhaustive finite instance of the oral-message model: known sender identities, detectable missing messages, fixed rounds, and at most one Byzantine participant. It does not cover signatures, unknown senders, unbounded delays without a round interpretation, or arbitrary n and fault counts. The case argument, rather than the scenario count alone, explains the mechanism behind this small instance of the paper's construction.
Check your reasoning
- Enumerates all 83 specified scenarios including omissions and equivocating relays.
- Checks agreement and loyal-commander validity as separate conditions.
- Explains both fault cases and limits the claim to the stated model.
2. Counterexample · allow 40 minutes
Break two tempting tie rules
Try the same direct-plus-relay idea with only C, A, and B and at most one faulty participant. Each lieutenant receives two candidate values: its direct order and the other's relay. On a tie, first try defaulting to 0. Then try preferring the direct order.
For each rule, construct a complete message trace violating either loyal-commander validity or agreement. Name the loyal participants and show their local vectors and decisions. Explain why these two counterexamples do not by themselves establish impossibility for every conceivable three-participant oral-message protocol.
Get a starting hint
For the default rule, make a loyal commander's order disagree with the default. For the direct-preference rule, let a faulty commander send different orders to two loyal lieutenants.
Compare your reasoning with the worked solution
For default-to-0, let C and A be loyal, let C order 1, and let B be faulty. C sends 1 to both. A faithfully relays 1 to B, while B tells A that it received 0. A's local vector is (direct 1, relay 0), a tie. It decides 0. The only loyal lieutenant has disobeyed a loyal commander, so validity fails. Agreement alone would miss this failure because there is only one loyal lieutenant.
For direct preference, let C be faulty and A and B be loyal. C sends 0 to A and 1 to B. Their faithful relays give A the vector (0,1) and B the vector (1,0). Each tie is resolved by its own direct value, so A decides 0 and B decides 1. Agreement fails, even though every lieutenant followed the rule correctly.
These traces expose why a local tie policy cannot repair this particular two-entry scheme. They do not constitute the paper's full lower-bound proof: ruling out every protocol requires an indistinguishability argument about what loyal participants can observe across multiple executions, rather than a list of unsuccessful algorithms. Nor do the traces apply unchanged to the paper's signed-message model, where an unforgeable signature changes which evidence a participant can relay and authenticate. A sound conclusion names the protocol class and assumptions actually tested.
Check your reasoning
- Provides a default-rule validity failure with C ordering 1.
- Provides a direct-preference agreement failure with a faulty commander.
- Avoids presenting two failed algorithms as a universal impossibility proof.
Check your understanding
In the faulty-commander trace, why do loyal lieutenants agree?
- Every direct order is identical.
- The commander is necessarily detected and repaired.
- All loyal relays expose the same vector and use the same choice rule.
- A signature prevents all faulty behavior.
Explanation
With the commander as the only fault, the lieutenants relay faithfully and reconstruct matching evidence.
Which observation tests validity rather than agreement alone?
- All loyal lieutenants preserve the loyal commander’s order.
- All loyal lieutenants choose the same default, regardless of the order.
- All loyal lieutenants receive the same number of messages.
- The commander learns which lieutenants disagree.
Explanation
Agreement alone could be achieved by always choosing a default; validity connects the result to a loyal sender.
Original paper and sources
Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 1982.
Read the original paper →Read the primary paper: Leslie Lamport
- The Byzantine Generals Problem: Leslie Lamport