Understanding a concurrent program requires identifying invariants—boolean-valued properties of the state that, if true at each step, guarantee the output is correct—and reasoning about invariants rather than behavioral sequences reduces complexity from exponential to quadratic in the number of processes.
causalpending
Speaker
Leslie LamportEvidence Quote
“The only thing that that tells the program what to do next is its current state. And the way to understand uh a program is to say what is the property of the state at each point that ensures that the answer it produces is correct—that property which is mathematically a boolean valued function of the state is called an invariant.”
Source
Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport— Ryan PetermanCreated: 8/12/2026, 6:17:50 PM
My Notes
Loading notes...