Before Blockchains, There Was State Machine Replication
Barbara Liskov, a Turing Award winner, discusses her pioneering work in distributed systems, including view stamp replication and Practical Byzantine Fault Tolerance (PBFT), which laid the foundation for modern blockchain protocols. She traces her career evolution from programming languages to distributed computing, and explains how these foundational protocols enable reliable systems even when components fail or act maliciously.
Summary
Barbara Liskov recounts her transition into distributed systems research in the early 1980s after completing work on programming languages and data abstraction. She was inspired by Bob Kahn's vision of distributed computing and saw an opportunity to tackle an unsolved problem. Her early work on Argus extended her previous language design by introducing guardians—objects residing at network nodes that could be called remotely—enabling the study of concurrent, distributed programs with atomic transactions.
Viewstamp replication emerged from practical needs: replicated file systems were desirable for collaborative work and system resilience, but existing approaches relied on locking mechanisms Liskov considered impractical. Working with student Brian Oki, she developed viewstamp replication to solve the critical problem of two-phase commit's vulnerability window: if the primary failed, the entire system halted. The solution introduced a view-change protocol where backups could elect a new primary while preserving the complete transaction history, effectively creating a distributed ledger.
Viewstamp replication initially handled only benign failures (silent or crashed machines). The shift to Byzantine fault tolerance came through DARPA funding aimed at addressing malicious internet attacks in the late 1990s. Student Miguel Castro proposed extending replication to handle Byzantine failures, where replicas could lie or send corrupt messages. This required 3F+1 replicas instead of 2F+1, and introduced the critical innovation of certificates—sets of 2F+1 signed messages proving consensus—ensuring no single replica could be trusted.
Liskov emphasizes that modularity and abstraction principles from her programming language work directly informed her distributed systems research. She values the interplay between theory and practice, noting that theoretical computer science provided essential tools (like cryptographic certificates) while practical systems work demonstrated feasibility through benchmarks. She acknowledges MIT's environment but suggests other strong institutions could have achieved similar results, emphasizing that teaching and research are synergistic—both require understanding from first principles.
The transcript also covers the delayed adoption of these protocols (10 years for viewstamp replication before widespread use) and the eventual importance to blockchain systems, which she initially didn't anticipate. Liskov addresses concerns about AI's impact on computer science education and the future of coding, arguing that verification, specification, and design at higher abstraction levels will become increasingly important as AI handles lower-level implementation details.
About this episode
Every blockchain today relies on replication techniques first developed in the 1980s by researchers who weren't thinking about cryptocurrencies at all. In this episode, Tim Roughgarden speaks with MIT professor and Turing Award winner Barbara Liskov, one of the pioneers of programming languages, fault tolerance, and distributed systems. Joined by a16z crypto research partner Ittai Abraham, they trace the evolution of ideas that now underpin modern blockchain networks. The conversation explores viewstamped replication, Practical Byzantine Fault Tolerance (PBFT), state machine replication, and why concepts developed decades before Bitcoin became the foundation for today's blockchain protocols. Along the way, Liskov reflects on the relationship between theory and practice, the importance of modularity and formal reasoning, and why AI is creating a new generation of systems research.
Key Insights
- Liskov identified that the systems community's locking-based approach to replication was impractical because it depended on distant users behaving correctly, leading her to shift responsibility to the replicas themselves through atomic transactions.
- The two-phase commit protocol had a critical vulnerability called the 'embarrassing pause' where system failure at the primary would halt the entire system, which viewstamp replication solved through a view-change protocol that preserved transaction history.
- Viewstamp replication and Paxos were independently developed solutions to the same problem that went unrecognized as equivalent for years, only later identified when they appeared in the Google File System paper.
- Byzantine fault tolerance required 3F+1 replicas instead of 2F+1 because the system must never trust any individual replica and instead rely on proof from the group through cryptographic certificates of 2F+1 signed messages.
- PBFT required an additional phase beyond viewstamp replication where the primary can only suggest the next step, then 2F+1 replicas must together agree and commit it, solving the problem of a potentially lying primary.
- State machine replication abstracts away application-specific logic, treating only the ordering of operations as critical, enabling the same consensus protocol to serve different applications and execution engines.
- DARPA funding specifically targeting malicious internet attacks in the late 1990s directly catalyzed the development of Byzantine fault tolerance protocols, demonstrating how government research priorities can shape research directions.
- Liskov argues that future coding work will shift from low-level implementation to higher-level design, specification, and verification as AI handles routine code generation, requiring programmers to understand systems deeply enough to validate AI-generated code.
Topics
Transcript
DARPA had recognized that this was a serious problem, the problem of malicious attacks, and was looking for research in that area. I had a student, Miguel Castro, he came to me and he said, why don't we see whether we can figure out a way to do replication that handles these malicious attacks, and that seemed like a great idea. The problem, if the primary failed, the primary that was running the protocol, the whole thing came to a crashing halt. We came up with a protocol that if the primary seemed to not be doing its job, the backups then carried out another protocol in which a different replica became the primary. We thought that at some point…
Full transcript available for MurmurCast members
Sign Up to AccessMore from The a16z Show
The Top 100 Consumer AI Apps: Who’s Actually Paying?
A16Z's seventh edition Top 100 Consumer AI Apps Report reveals that while half of Americans use AI, only 4.5% pay for subscriptions, with spending heavily concentrated among developers and power users. The report highlights emerging personal agents as a major trend, significant divergence between ChatGPT, Claude, and Gemini, and substantial untapped opportunities in categories like dating, social, shopping, and entertainment.
David George & Jack Altman on AI, Autonomy, and the Next $25 Trillion
David George from Andreessen Horowitz argues that AI, autonomy, and robotics will create over $25 trillion in market value over the next decade, with success across multiple layers of the stack—frontier models, open source, and applications will all flourish due to massive supply constraints and early-stage demand penetration among knowledge workers.
Beyond the God Model | Alex Atallah & Amjad Masad
Alex Atallah (OpenRouter) and Amjad Masad (Replit) discuss how the future of AI development lies in specialized, diverse models working together rather than relying on single AGI-like models. They argue that enterprises need independence from foundation model providers through model diversity, cost efficiency, and ownership of their own AI capabilities, while also addressing the risks of general-purpose agents and the importance of model specialization.
Why AI Agents Can Beat the Incumbents
Leo, an AI-native startup, is building multi-agent systems to automate end-to-end procurement processes for enterprises by coordinating work across multiple departments, stakeholders, and external systems that traditional procurement software cannot handle. The company differentiates itself from incumbents by owning the entire job workflow rather than being confined to a single system of record, and builds customer trust through human-in-the-loop approaches before scaling to fully autonomous negotiations.
The $1 Trillion AI Buildout | State of Markets
A16Z partners discuss the $1 trillion AI infrastructure buildout, arguing it's driven by real earnings growth rather than inflated valuations, with adoption still extremely early at the enterprise level. They highlight opportunities across consumer agents, robotics, autonomous vehicles, and enterprise diffusion, while noting that the market's 90% gain since ChatGPT reflects fundamental business performance rather than speculative excess.