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
How Bitcoin Rewired a Classic Computer Science Problem
This episode explores how Bitcoin solved the Byzantine fault tolerance problem, a foundational challenge in distributed computing studied for 40 years, and traces how decades of academic research in consensus protocols are now directly informing the design of modern blockchain systems. The conversation highlights the convergence of classical distributed computing theory with practical blockchain implementations, particularly through the transition from proof-of-work to proof-of-stake protocols.
Mark Zuckerberg & Priscilla Chan: How AI Will Help Cure Disease
Mark Zuckerberg and Priscilla Chan discuss the Chan Zuckerberg Initiative's focus on accelerating scientific discovery through AI and biology tools rather than individual therapies. They explain their strategy of building shared infrastructure, data sets, and virtual cell models over 10-15 year horizons to enable faster progress against disease.
Adam Neumann: This Is How You Build Iconic Companies
Adam Neumann discusses his journey from a difficult childhood in Israel through the WeWork collapse to building Flow, a vertically integrated real estate company reimagining residential living through technology, design, and community. Mark Andreessen and Ben Horowitz explain why they backed Neumann post-WeWork, emphasizing how founders who overcome profound challenges often have the greatest potential, and detail Flow's expansion strategy across the US and Saudi Arabia.
Is Software Losing Its Head?
The podcast discusses how enterprise software is fundamentally shifting from being built around human interfaces to becoming 'headless'—optimized for AI agents to access data and logic directly. While incumbents like Salesforce are rebranding existing APIs as agent-ready, the real opportunity lies in new companies building between legacy vendors, leveraging AI to bridge organizational silos and capture the exceptions and context that make enterprise software truly sticky.
Don’t Follow Your Passion | Ben Horowitz’s Advice for New Graduates
Ben Horowitz argues against the conventional "follow your passion" advice for graduates, instead advocating for independent thinking and following your contribution. He emphasizes that success often creates passion rather than the reverse, and that the greatest opportunities lie in thinking original thoughts that contradict prevailing beliefs.