Before Blockchains, There Was State Machine Replication (ft. Barbara Liskov and Tim Roughgarden)

Barbara Liskov moved into distributed systems around 1980 after completing the Clu programming language, motivated by a paper from Bob Kahn describing distributed computing across network nodes. Her follow-on language, Argus, introduced a construct called a guardian that resided at a single node and exposed operations callable from other nodes, and it adopted transactions and two-phase commit from database systems to ensure distributed computations either completed fully or had no effect.

Viewstamp Replication emerged in the mid-1980s from the systems community's interest in replicated file systems that stayed available when individual machines failed. The prevailing approach relied on users applying locks across replicas, which was fragile because it depended on remote sites behaving reliably. Theoretical computer science had already established that two F plus one replicas are needed to survive F failures, and two-phase commit had a known vulnerability where failure of the primary halted the entire protocol. Viewstamp Replication, developed with PhD student Brian Oki, solved this by introducing a view change protocol in which backups detect a failing primary and elect a new one, while guaranteeing that everything reaching the commit point in the previous view was preserved with identical history in the new view. Liskov described the protocol as a distributed log, directly analogous to a single-machine write-ahead log used for crash recovery.

Viewstamp Replication was published in the late 1980s and was developed independently from Paxos, which Leslie Lamport was working on at roughly the same time. Liskov heard Lamport give a talk on Paxos in the 1980s and did not understand it, and she noted the lack of understanding was mutual. The protocol addressed only benign failures where machines are either running or completely silent, because Byzantine failures were not a practical concern on the Arpanet at the time. Adoption was slow, but a former Liskov student at Google, Bill Weil, later recognized that the Google file system's replication approach was essentially Viewstamp Replication.

Practical Byzantine Fault Tolerance originated when PhD student Miguel Castro found a DARPA solicitation seeking solutions to malicious attacks on the internet, which DARPA had identified as a serious emerging problem. PBFT was built directly on top of Viewstamp Replication and extended it to handle Byzantine failures where replicas can lie rather than simply going silent. Byzantine fault tolerance requires three F plus one replicas instead of the two F plus one needed for benign failures. PBFT adds one extra phase compared to Viewstamp Replication because the primary can only suggest the next step and two F plus one replicas must collectively confirm it before committing. A certificate in PBFT consists of two F plus one signed messages all asserting the same thing, serving as proof that a particular point in the protocol was reached. Liskov noted the certificate concept was drawn from prior theoretical computer science work rather than invented by the PBFT team, and cryptography was adopted immediately to ensure message integrity and sender authentication.

The separation of consensus from execution was fundamental to Viewstamp Replication from the beginning. State machine replication treats the application as a black box and focuses only on ordering operations, not on what executing those operations means. Roughgarden described Ethereum and Solana as among the most literal implementations of the fully general state machine replication problem seen today. Roughgarden also noted that PBFT is viewed as a bridge from theoretical Byzantine fault tolerance work to practical systems, and that the certificate idea for proving transaction ordering appears in many major blockchain protocols. After finishing PBFT, Liskov and Castro expected eventual adoption given that Viewstamp Replication itself had experienced roughly a ten-year delay before widespread use. Roughgarden observed that by 2025 it is well understood among blockchain practitioners and researchers that PBFT and protocols like it are the foundation for what those systems do, though the blockchain community took several years after Bitcoin to recognize that PBFT-style protocols were the right tool. Liskov noted that Bitcoin's protocol looks rather different from PBFT and from most consensus protocols developed prior to it.

Roughgarden described a line of work from the past five to seven years on accountability showing that consistency violations in Byzantine fault tolerant systems can only be created by signing inconsistent things, which allows identification of bad actors who double-signed conflicting states.

Liskov expressed concern that AI is putting computer science in a strange place regarding research directions and the job market for young coders. She noted that AI can write small programs from specifications but those programs may be wrong, which creates demand for verification tools and requires students to understand how to write programs themselves in order to evaluate AI-generated code. She described the future role for coders as working at a higher level managing AI-generated code rather than writing low-level code directly.