
Lessons from Leslie Lamport
Leslie Lamport created LaTeX and developed Paxos. His work emphasizes precise descriptions and clear reasoning when designing software, especially concurrent systems. — A Discussion with Leslie Lamport.
Part 1: The Relationship Between Writing and Thinking
- On the nature of thought: Thinking and specifications reduce errors; they do not guarantee bug-free software. — Why We Should Build Software Like We Build Houses.
- On the connection between writing and logic: Lamport credits Dick Guindon’s observation that writing exposes unclear thinking, and applies it to specifications. — Why We Should Build Software Like We Build Houses.
- On the limits of memory: Writing down an argument exposes details and gaps that are easy to overlook mentally. — Peterman Interview.
- On the purpose of a specification: A specification states what software should do before implementation begins. — Why We Should Build Software Like We Build Houses.
- On language as a distraction: Distinguish computational ideas from the particular language used to express them. — Computer Science and State Machines.
- On the difficulty of precision: Practice specifying the problem a system must solve before presenting an algorithm. — Teaching Concurrency.
- On prose vs. math: For precise concurrent algorithms, use mathematical descriptions rather than relying only on prose or code. — Quanta Interview.
- On the value of abstractions: Abstraction rises above implementation details to make complex designs understandable. — Why We Should Build Software Like We Build Houses.
Part 2: The Logic of Distributed Systems
- On the definition of distributed failure: Remote dependencies can make a local computer unusable when an unfamiliar machine fails; investigate those dependencies. — Distributed-Systems Email, May 1987.
- On reaching consensus: Consensus must preserve agreement despite the specified process and communication failures. — Paxos Made Simple.
- On the Byzantine Generals problem: Lamport, Shostak and Pease’s oral-message model requires more than two-thirds loyal participants; unforgeable signatures change that bound. — The Byzantine Generals Problem.
- On the origin of Paxos: The Greek-parliament story made Paxos memorable but obstructed readers’ understanding; Lamport later regretted that communication failure. — A Discussion with Leslie Lamport.
- On the necessity of state machines: Model computation with states, initial states and permitted transitions, including hidden control state. — Computer Science and State Machines.
- On replicated logs: Deterministic replicas produce matching states and outputs when they execute the same chosen command sequence. — Paxos Made Simple.
- On the Bakery Algorithm: The Bakery algorithm tolerates arbitrary values from reads overlapping a write, with a single writer per memory location. — Peterman Interview.
- On fault tolerance: Replicate the state machine so service does not depend on a single central server remaining available. — Paxos Made Simple.
- On complexity and errors: Abstract algorithms can make concurrency reasoning tractable when the corresponding implementation contains thousands of lines. — The Temporal Logic of Actions.
Part 3: Formal Specification and TLA+
- On the utility of TLA+: TLA+ builds system descriptions on ordinary first-order logic and set theory, with temporal operators where needed. — High-Level Specifications: Lessons from Industry.
- On finding bugs: AWS engineers reported that TLA+ exposed subtle design bugs missed by reviews and testing; this did not prove the executable code correct. — How AWS Uses Formal Methods.
- On the definition of 'Liveness': Safety constrains what may happen; liveness requires specified progress eventually, under the model’s environmental assumptions. — How AWS Uses Formal Methods.
- On mathematical tools: Use elementary sets, functions and logic to express specifications precisely. — Why We Should Build Software Like We Build Houses.
- On the resistance to math: Fear of mathematics and the pressure to avoid upfront effort can obstruct adoption of formal specifications. — Quanta Interview.
- On invariants: An invariant holds in every reachable state; an inductive proof establishes it initially and preserves it across steps. — Teaching Concurrency.
- On the Temporal Logic of Actions: Describe a system and its required properties in one logic, expressing correctness through logical implication. — The Temporal Logic of Actions.
- On model checking: Model checking explores a specified model; its usefulness depends on capturing the real system’s significant behavior. — How AWS Uses Formal Methods.
- On blue prints: Use specifications as software blueprints; match their formality to the project. — Why We Should Build Software Like We Build Houses.
- On the cost of formality: Specifications can make later changes easier by documenting intended behavior and interfaces. — Why We Should Build Software Like We Build Houses.
Part 4: Programming vs. Coding
- On the distinction between roles: Producing code is distinct from establishing that an algorithm behaves correctly. — Quanta Interview.
- On the obsession with languages: Ordinary mathematics can reveal relationships that programming-language notation obscures. — Computer Science and State Machines.
- On clear design: Treat a program as a mathematical object whose intended meaning can be examined logically. — The Future of Computing: Logic or Biology?.
- On simplicity: Avoid unnecessary complexity so systems remain understandable. — The Future of Computing: Logic or Biology?.
- On trial and error: Use particularly rigorous descriptions where correctness matters, including chips and concurrent cloud infrastructure. — Quanta Interview.
- On the definition of 'Algorithm': An algorithm’s mathematical description can expose its behavior independently of its pseudocode. — Computer Science and State Machines.
- On the role of comments: Lamport describes extensive comments, documentation and specifications in his own code—not eliminating documentation once a spec exists. — Software Engineering Radio 203.
Part 5: Time, Order, and Causality
- On logical clocks: Logical clocks assign timestamps consistent with happened-before; a later timestamp alone does not establish causality. — Time, Clocks, and the Ordering of Events.
- On the 'Happened-Before' relation: Happened-before follows local process order, message send-to-receive order, and their transitive consequences. — Time, Clocks, and the Ordering of Events.
- On synchronization: Lamport’s synchronization example orders resource requests so processes can coordinate access without a central scheduler. — Time, Clocks, and the Ordering of Events.
- On physical time: Physical clocks can support ordering when their synchronization and drift meet explicit assumptions; logical clocks do not abolish physical time. — Time, Clocks, and the Ordering of Events.
- On total ordering: Order by logical timestamps, breaking ties with a chosen process order, to extend the causal partial order. — Time, Clocks, and the Ordering of Events.
- On the limits of observation: Events unrelated by happened-before lack a causally determined order within that model—not necessarily a physical chronology. — Time, Clocks, and the Ordering of Events.
- On message delays: Paxos separates safety from progress in a model allowing delayed, duplicated or lost messages—not corrupted messages. — Paxos Made Simple.
Part 6: LaTeX and Documentation
- On the creation of LaTeX: Lamport developed macros while writing a book, then made the additional effort to make them useful to others. — LaTeX E-Interview.
- On the philosophy of LaTeX: Concentrate on a document’s ideas and logical structure, not cosmetic formatting. — Document Production: Visual or Logical?.
- On macros: Describe logical elements with semantic macros so their presentation can be changed consistently. — Document Production: Visual or Logical?.
- On open source: LaTeX was freely distributed; Lamport also published a successful paid manual. — LaTeX E-Interview.
- On standardizing science: Mittelbach traces LaTeX’s spread to stable, documented releases and high-level document descriptions—not a guarantee of scientific precision. — LaTeX Anniversaries.
- On simplicity for the user: Let trained design choices format logical structures consistently rather than requiring authors to design every element. — Document Production: Visual or Logical?.
- On the durability of tools: LaTeX’s longevity combines a stable core with extensions, maintenance and deliberate consolidation of incompatible variants. — LaTeX Anniversaries.
Part 7: Mathematical Rigor and Algorithms
- On the definition of 'Obvious': When a proof step seems obvious, examine it one level deeper to expose hidden gaps. — Making Math More Rigorous.
- On the beauty of a proof: Name facts and structure proof steps so readers can follow the reasons supporting each conclusion. — How to Write a 21st Century Proof.
- On rigorous thinking: Precise mathematical descriptions help engineers reason about concurrent executions instead of relying on informal intuition. — Teaching Concurrency.
- On 'Hand-wavy' reasoning: Structured proofs expose assumptions and dependencies; improving their rigor does not require making every proof machine-checked. — How to Write a 21st Century Proof.
- On the role of logic: Explicit logical notation can make mathematical statements easier to manipulate and their negations easier to compute. — Making Math More Rigorous.
- On set theory: Basic sets, functions and predicate logic suffice for the state-machine descriptions Lamport advocates—not every computer-science problem. — Teaching Concurrency.
- On persistence: After an editor identified a bug in his mutual-exclusion algorithm, Lamport persisted and developed the Bakery algorithm. — Peterman Interview.
- On the limits of intuition: An initially convincing concurrent algorithm can still be wrong; Lamport’s rejected solution taught him to demand a correctness argument. — Peterman Interview.
Part 8: Education and the Future of Computing
- On teaching students: Teach students to specify problems and reason about computations; assess what they can do, not accumulated facts. — Teaching Concurrency.
- On the shift to biology: Lamport warns against surrendering understanding to biological-style evolution; he favors logical design of dependable software. — The Future of Computing: Logic or Biology?.
- On the responsibility of engineers: As society depends more on software, developers must strive to understand systems well enough to make them dependable. — The Future of Computing: Logic or Biology?.
- On learning from history: Connect mathematical foundations with real engineering practice rather than abandoning them after an introductory course. — The Future of Computing: Logic or Biology?.
- On the value of math in school: Help students use logical notation to investigate mathematical statements, rather than treating notation as unfamiliar decoration. — Making Math More Rigorous.
- On the next generation: Develop intellectual tools that help people understand systems as their complexity grows. — A Discussion with Leslie Lamport.
- On the definition of 'Science': Lamport treats computation as a central subject of computer science and state machines as a unifying description. — Computer Science and State Machines.
- On the ultimate goal: Seek understandable software that behaves consistently, instead of accepting unexplained failures as inevitable. — The Future of Computing: Logic or Biology?.