state machine
An abstract system with a state and transitions between states; each command takes the current state and produces a new state and output value
As defined in Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
Where it comes up · 1
- Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport7 claims
Most important claims · 7 of 7Search all claims for “state machine” →
- The Byzantine generals problem arose from Lamport's work on fault-tolerant state machines at SRI, where the challenge was how systems could reach agreement when some processes might fail arbitrarily (do 'anything')—including sending malicious or contradictory messages.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Lamport's initial Byzantine generals algorithm used digital signatures, which allowed it to tolerate one faulty process with three total processes, whereas algorithms without signatures required four processes—a critical difference for practical systems.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- A state machine is defined by its state and a next-state relation: each command takes the system from one state to another, with correctness determined by invariants—boolean-valued properties of the state that ensure correct output regardless of what happened in the past.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Computer people and programmers are 'really hung up on languages,' inventing languages and believing they improve thinking, but for understanding and reasoning about systems, mathematics beats any programming language.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- In the Time, Clocks paper, Lamport described systems in terms of state machines—entities with a state that processes commands in order, where each command changes state and produces a value—and recognized this was the most important idea in the paper, but it was completely ignored by readers.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- State machines are more powerful than Turing machines because they can describe impossible or nondeterministic systems, whereas Turing machines only describe feasible computations—a feature, not a bug.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Lamport now believes that state machines (described not with commands and values but simply as a state and a next-state relation) are the 'Turing machine of concurrency'—the foundational abstraction for concurrent computing.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport