The Two Generals' Problem
Two armies must attack at the same moment. Any message can be lost, including the one confirming the last one arrived.
1975 (proved), 1978 (named)18 min read
Nature
Impossibility result
Mathematically established. Not paradoxical in the strict sense, but almost always experienced as one because the impossible thing feels achievable.
A theorem proving no solution can exist.
7 entriesFilter these further →
Intermediate
Curious teenagers and general adult readers.
Advanced
Undergraduate level in the relevant field.
The Halting Problem
No program can ever be written that reliably tells you whether another program will finish running. This is not a limit of our cleverness.
193620 min read
The Byzantine Generals Problem
Several generals must attack together or be destroyed. They can only send messengers, and some of the generals are traitors.
198222 min read
The CAP Theorem
A system spread across several machines can give you consistent answers, or always answer at all. The network makes you choose.
2000 (conjectured), 2002 (proved)23 min read
Expert
Graduate level or specialist readers.
Gödel's Incompleteness Theorems
In any system of arithmetic strong enough to be useful, there are true statements it can never prove. Including this one.
193125 min read
Arrow's Impossibility Theorem
There is no fair way to turn what a group of people each want into what the group wants. This is not a complaint about politics. It is a theorem.
1950 (paper), 1951 (book), 1963 (corrected second edition)25 min read
The FLP Impossibility Result
A handful of computers cannot be guaranteed to agree on a single value if even one of them might be slow. Not merely hard — impossible.
198523 min read