In this episode of First Principles by a16z Crypto, host Tim Roughgarden (Head of Research) and research partner Itay Abraham sit down with Turing Award-winning computer scientist Dr. Barbara Liskov. As an MIT professor, Liskov pioneered foundational concepts in programming languages and distributed systems, including data abstraction and replication protocols.

The conversation traces Liskov's career path, starting with her transition from the CLU programming language to Argus in the early 1980s, where she integrated transactions and concurrency. She details the creation of Viewstamped Replication to solve two-phase commit vulnerabilities, the parallel discovery of Paxos, and the development of Practical Byzantine Fault Tolerance (PBFT) in the late 1990s to counter malicious internet attacks.

Finally, Liskov reflects on the connection between mathematical proofs and modular programming. She discusses the future of computer science education in the age of AI, emphasizing that students must master high-level system design, modularity, and verification as outlined in her seminal work with John Guttag, Abstraction and Specification in Program Development.

From Modular Programming to Distributed Systems

Liskov transitioned from her sequential language CLU to Argus in the early 1980s to explore parallel computing and distributed systems.

"Modularity is everything in building large programs" - Barbara, explaining how modular software design mirrors mathematical proofs with independent lemmas.

Argus introduced "guardians" as abstract data types residing at single network nodes, utilizing atomic transactions and two-phase commit protocols to manage concurrency and node failures.

The Genesis of Viewstamped Replication and Paxos

Developed in the mid-1980s with student Brian Oakey, Viewstamped Replication aimed to build a highly available, replicated file system.

The protocol resolved the "embarrassing pause" or "window of vulnerability" of two-phase commit by introducing a primary-backup system that could transition to a new "view" if the primary failed.

Viewstamped Replication and Leslie Lamport's Paxos were developed independently around the same time, representing identical solutions to the same fundamental replication problem.

Early replication protocols only focused on benign failures where "machines were either running or they were completely silent" - Barbara.

Bridging Theory and Practice with Practical BFT

In the late 1990s, Liskov and her PhD student Miguel Castro developed Practical Byzantine Fault Tolerance (PBFT) in response to a DARPA request for proposals targeting malicious internet attacks.

While benign failures require 2F+1 replicas to tolerate F failures, Byzantine environments require 3F+1 replicas to defend against nodes that actively lie.

"You never trust an individual replica. You only trust the group" - Barbara, explaining how PBFT uses certificates of 2F+1 signed messages to prove protocol state transitions.

PBFT served as a critical bridge, demonstrating that theoretical Byzantine consensus concepts could be implemented as highly performant, practical systems.

State Machine Replication and the Blockchain Era

Liskov designed her replication protocols around the State Machine Replication (SMR) paradigm, separating the ordering of ledger operations from their execution.

"We came up with PBFT, we thought that at some point people would start to use this. And then along came blockchains." - Barbara, noting the decade-long delay before widespread adoption.

Modern Turing-complete blockchain protocols like Ethereum and Solana represent literal, fully general implementations of the state machine replication paradigm.

The Future of Coding and System Design Under AI

Liskov expresses concern over AI-generated code, noting that developers must still understand how to program manually to verify AI outputs for correctness.

Future software engineers will shift from writing low-level loops to managing code at a higher level of abstraction, design, and verification.

The core principles of design, modularity, and specifications taught in Abstraction and Specification in Program Development remain essential for navigating the future of software engineering.