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
Inside Cursor: The Anatomy of a Generational Startup
This episode from the a16z podcast discusses Cursor's remarkable rise from an early-stage startup to a leading AI coding company, examining the founders' product-focused philosophy, strategic decisions to build an independent IDE rather than a plugin, and their ability to compete against entrenched players like Microsoft while eventually being acquired by Elon Musk's company. The conversation highlights how Cursor maintained focus, built a distinctive culture, executed sophisticated hiring and M&A strategies, and navigated an intensely competitive landscape.
The State of AI: Macro, Apps, and Consumer
Anish Acharya discusses how AI is shifting from a model-centric competition to an application-centric market, where multiple frontier models will coexist and applications capturing economic value for specific domains. Consumer AI is entering a renaissance phase with personal agents and coding tools enabling new business formation and improved quality of life.
The New Economics of AI | Martin Casado & Steven Sinofsky
Martin Casado and Steven Sinofsky discuss how AI is fundamentally shifting the computing industry from an engineering-constrained problem to a capital-constrained one, examining what recent AI breakthroughs in mathematics actually indicate about economic value creation and the changing competitive dynamics between startups and incumbents.
Why Medical AI Needs a Referee | Protege's Engy Ziedan
Engy Ziedan, co-founder of Protégé, argues that medical AI faces a critical evaluation gap: models can ace benchmark exams but fail in real clinical settings, and independent oversight is essential because hundreds of millions use AI for health advice with no one ensuring safety or correctness. Protégé is positioning itself as an impartial referee to continuously evaluate AI models in healthcare through real-world data rather than static benchmarks.
Martin Casado on Where the Value Is Going in AI
Martin Casado discusses how AI has fundamentally changed venture capital economics by enabling small teams to productively deploy massive amounts of capital directly into growth, using recent acquisitions like Cursor ($60B) and OpenRouter by Stripe as examples of value accruing across the AI stack rather than consolidating entirely at frontier labs.