2. The Byzantine Generals, and why it was impractical
An old problem with a memorable name
The problem PBFT solves is not new. It was posed and named in 1982 by Leslie Lamport, Robert Shostak, and Marshall Pease, in a paper called "The Byzantine Generals Problem," and the framing is the reason the field now uses the adjective. Picture several divisions of an army camped around a city, each commanded by a general, able to communicate only by messenger. They must agree on a single plan, attack or retreat, and act together, because a half-hearted attack is worse than either. The difficulty is that some of the generals may be traitors, actively trying to prevent the loyal ones from agreeing, and free to send one message to one general and the opposite to another. The requirement is that the loyal generals all decide on the same plan regardless of what the traitors do.
That is the abstract shape of every Byzantine-tolerant system, including the compromised server and the corrupted replica of the previous chapter. The traitorous general is the equivocating node. And Lamport rewards attention here, because he is the recurring author of this thread: he gave the field logical clocks and state-machine replication, he gave it Paxos, and he gave it the Byzantine Generals. The consensus story runs through him from beginning to end, and this final seminar builds on the problem he named.
The bound was known, and so was the bad news
The 1982 work, together with an earlier 1980 paper by the same authors, settled the fundamental limit. To tolerate f traitors when messages are unsigned, you need at least 3f+1 generals; with fewer, the loyal generals provably cannot always agree. That number, the one this seminar spends its central chapter on, was established roughly seventeen years before PBFT. This matters for reading PBFT honestly. Castro and Liskov did not discover that Byzantine agreement is possible, and they did not discover the 3f+1 bound. Both were old results. What they discovered was how to make it usable.
Because the bad news, for two decades, was that Byzantine agreement was a beautiful theory you could not afford to run. The classical algorithms assumed a synchronous system, one where message delays and processing times have known bounds, so the protocol can proceed in tidy rounds and treat a missing message as a detected fault. Real networks, and the internet in particular, are not synchronous; messages can be arbitrarily delayed, and you cannot tell a slow node from a dead one, which is the world the fourth seminar described. The algorithms that did aim at real systems, like Rampart and SecureRing in the mid-1990s, still leaned on synchrony assumptions or failure detectors, and they were slow, expensive enough that no one would put them under a working service. Byzantine tolerance was something you proved, not something you deployed.
Practical is the contribution
This is why the first word of the title is doing all the work. PBFT's contribution is not the possibility of Byzantine agreement but its practicality: an algorithm that is safe in a fully asynchronous network, that needs only a weak assumption about timing to make progress, and that runs fast enough to use. The paper reports improving on the response time of previous algorithms by more than an order of magnitude, and backs it with a real Byzantine-fault-tolerant file system that costs only a few percent over an unreplicated one. The theory had existed since 1982. The engineering that made it deployable is what 1999 added, and it is why this paper, rather than the founding one, is the seminar.
There is a boundary the previous seminars already drew and this one inherits. Even made practical, Byzantine agreement cannot escape the impossibility that the fourth seminar named: in a fully asynchronous system, no deterministic protocol can guarantee both safety and progress if nodes can fail. (Randomized protocols, like the later HoneyBadgerBFT, are the known way around it, at a price.) PBFT lives inside that limit just as Paxos did, and the next chapters will show how. First, though, the number, because the jump from crash tolerance to Byzantine tolerance is written most clearly in a single change to the arithmetic of quorums.
Principle: A problem can be solved in theory for decades and remain unsolved in practice, and closing that gap is a real contribution, not a footnote. "It can be done" and "it can be done fast enough to use" are different theorems, and systems live on the second one.