Two Generals & Byzantine Problems

The two foundational impossibility results in distributed systems. Knowing them isn't trivia — they tell you exactly what's possible to build and what's not. Every distributed protocol you'll ever design is constrained by one of these two problems. Senior engineers cite them by name; junior engineers re-discover them by losing data in production.

Two armies camp on hills on either side of a city. They need to attack at the same time to win — alone, either is defeated. Generals communicate only by messengers, who can be captured.

General A sends "attack at dawn" via messenger. The messenger arrives. But A doesn't know if the messenger arrived. So A cannot attack — what if the message was lost?

B receives, sends back "OK, will attack at dawn." Same problem — B doesn't know if A got the ack. Now B cannot attack either.

A, on receiving the ack, sends "OK got your ack." Same problem one more time. The chain never terminates with both sides certain.

The result (Akkoyunlu, Ekanadham, Huber, 1975): there is no protocol over a lossy channel that lets both parties be 100% certain they will attack together. Coordination over an unreliable channel is provably impossible to make perfect.

Every TCP connection, every HTTP request, every database commit acknowledgment faces this. You cannot have guaranteed agreement over a network. So real systems pick:

• Best-effort — try once, accept loss. UDP, fire-and-forget logging.
• At-most-once with explicit acks — if uncertain, assume the worst (don't act). Used in idempotent reads.
• At-least-once with retries + dedup — assume best (re-send), let receiver dedup. The standard for message delivery.
• Probabilistic — accept that 99.999% is the best you can do, design around the rare missing case.

The interview answer when someone asks "can we guarantee X?" — recognize when X is two-generals-equivalent, then propose at-least-once + idempotency.

Two-generals assumes channels can lose messages. Byzantine (Lamport, Shostak, Pease, 1982) is worse: the channels are reliable, but some generals are traitors. They send conflicting messages — "attack" to one ally, "retreat" to another — to sow confusion.

The result: with N generals, you can tolerate at most (N-1)/3 traitors while still reaching consensus. With 4 generals, 1 can lie. With 7 generals, 2 can lie. With 10 generals, 3.

This is why blockchain consensus (Bitcoin, Ethereum) needs ⅔ honest majority — they're literally solving Byzantine generals where any node may be malicious.

Most production systems are crash-fault tolerant, not Byzantine-fault tolerant. They assume nodes either work correctly or crash — they don't lie. Raft and Paxos work in this model. Cheap; sufficient for almost all internal systems.

You need Byzantine tolerance when:

• Public blockchains — anyone can run a node, anyone can be malicious.
• Aerospace / safety-critical — Boeing 777 flight control runs Byzantine consensus across redundant computers.
• Multi-party financial systems — clearing houses where participants don't fully trust each other.
• Some military comms — original motivation for the research.

Cost: BFT consensus is significantly more expensive (more rounds, more messages, ⅔ vs majority). Don't pay for it without need.

The third foundational result, completing the trio: Fischer-Lynch-Paterson (1985) proved that in a fully asynchronous distributed system where even one node can crash, no deterministic consensus protocol can guarantee both safety and liveness.

Translation: you can have a protocol that's always safe (never decides wrong) but might never decide. Or always decides but might decide wrong. Not both, in the worst case.

Real systems escape FLP by adding assumptions:

• Partial synchrony — assume messages eventually arrive within some bound. Raft, Paxos use this. Real networks behave this way 99.99% of the time.
• Failure detectors — eventually accurate guesses about who's alive (see heartbeat).
• Randomization — use random delays so adversarial scheduling can't keep stalling progress (Raft's randomized election timeouts).

These three results — Two Generals, Byzantine Generals, FLP — define the entire shape of distributed-systems research. Every protocol works around them in some way.

Payment gateway implicitly faces Two Generals on every charge ack — solved with idempotency keys. Stock exchange uses crash-fault-tolerant consensus, not Byzantine, because matching engines are trusted. Distributed locking deals with Two Generals when the lock-server's response is lost.