Visual summary of operating lessons from Leslie Lamport.

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

  1. 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.
  2. 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.
  3. On the limits of memory: Writing down an argument exposes details and gaps that are easy to overlook mentally. — Peterman Interview.
  4. 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.
  5. On language as a distraction: Distinguish computational ideas from the particular language used to express them. — Computer Science and State Machines.
  6. On the difficulty of precision: Practice specifying the problem a system must solve before presenting an algorithm. — Teaching Concurrency.
  7. On prose vs. math: For precise concurrent algorithms, use mathematical descriptions rather than relying only on prose or code. — Quanta Interview.
  8. 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

  1. 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.
  2. On reaching consensus: Consensus must preserve agreement despite the specified process and communication failures. — Paxos Made Simple.
  3. 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.
  4. 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.
  5. On the necessity of state machines: Model computation with states, initial states and permitted transitions, including hidden control state. — Computer Science and State Machines.
  6. On replicated logs: Deterministic replicas produce matching states and outputs when they execute the same chosen command sequence. — Paxos Made Simple.
  7. On the Bakery Algorithm: The Bakery algorithm tolerates arbitrary values from reads overlapping a write, with a single writer per memory location. — Peterman Interview.
  8. On fault tolerance: Replicate the state machine so service does not depend on a single central server remaining available. — Paxos Made Simple.
  9. 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+

  1. 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.
  2. 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.
  3. 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.
  4. On mathematical tools: Use elementary sets, functions and logic to express specifications precisely. — Why We Should Build Software Like We Build Houses.
  5. On the resistance to math: Fear of mathematics and the pressure to avoid upfront effort can obstruct adoption of formal specifications. — Quanta Interview.
  6. On invariants: An invariant holds in every reachable state; an inductive proof establishes it initially and preserves it across steps. — Teaching Concurrency.
  7. 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.
  8. 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.
  9. On blue prints: Use specifications as software blueprints; match their formality to the project. — Why We Should Build Software Like We Build Houses.
  10. 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

  1. On the distinction between roles: Producing code is distinct from establishing that an algorithm behaves correctly. — Quanta Interview.
  2. On the obsession with languages: Ordinary mathematics can reveal relationships that programming-language notation obscures. — Computer Science and State Machines.
  3. On clear design: Treat a program as a mathematical object whose intended meaning can be examined logically. — The Future of Computing: Logic or Biology?.
  4. On simplicity: Avoid unnecessary complexity so systems remain understandable. — The Future of Computing: Logic or Biology?.
  5. On trial and error: Use particularly rigorous descriptions where correctness matters, including chips and concurrent cloud infrastructure. — Quanta Interview.
  6. On the definition of 'Algorithm': An algorithm’s mathematical description can expose its behavior independently of its pseudocode. — Computer Science and State Machines.
  7. 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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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

  1. 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.
  2. On the philosophy of LaTeX: Concentrate on a document’s ideas and logical structure, not cosmetic formatting. — Document Production: Visual or Logical?.
  3. On macros: Describe logical elements with semantic macros so their presentation can be changed consistently. — Document Production: Visual or Logical?.
  4. On open source: LaTeX was freely distributed; Lamport also published a successful paid manual. — LaTeX E-Interview.
  5. 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.
  6. 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?.
  7. 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

  1. On the definition of 'Obvious': When a proof step seems obvious, examine it one level deeper to expose hidden gaps. — Making Math More Rigorous.
  2. 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.
  3. On rigorous thinking: Precise mathematical descriptions help engineers reason about concurrent executions instead of relying on informal intuition. — Teaching Concurrency.
  4. 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.
  5. 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.
  6. On set theory: Basic sets, functions and predicate logic suffice for the state-machine descriptions Lamport advocates—not every computer-science problem. — Teaching Concurrency.
  7. On persistence: After an editor identified a bug in his mutual-exclusion algorithm, Lamport persisted and developed the Bakery algorithm. — Peterman Interview.
  8. 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

  1. On teaching students: Teach students to specify problems and reason about computations; assess what they can do, not accumulated facts. — Teaching Concurrency.
  2. 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?.
  3. 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?.
  4. 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?.
  5. 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.
  6. On the next generation: Develop intellectual tools that help people understand systems as their complexity grows. — A Discussion with Leslie Lamport.
  7. 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.
  8. On the ultimate goal: Seek understandable software that behaves consistently, instead of accepting unexplained failures as inevitable. — The Future of Computing: Logic or Biology?.