algorithm (vs. program)
An abstract description of a procedure independent of implementation language; algorithms can be realized in any programming language, whereas programs are concrete code written in a specific language
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 Lamport19 claims
Most important claims · 10 of 19Search all claims for “algorithm (vs. program)” →
- The bakery algorithm has the remarkable property that it does not require atomic (all-or-nothing) writes to shared memory: if one process reads a register while another is writing to it, the reader can get any arbitrary value and the algorithm still works correctly.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- The bakery algorithm was inspired by the deli ticket system, where customers take a numbered ticket and the lowest remaining number is served next, adapted to work without central control by having each process choose its own ticket number.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
- There was an eight-year gap between when Lamport developed the Paxos algorithm (in the late 1970s) and when the 'Part-Time Parliament' paper was finally published (in 1998), during which the paper sat with acceptance but no publication because the original referees thought it was 'okay' but 'not terribly important.'Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Lamport simplified Dijkstra's concurrent garbage collection algorithm by recognizing that the free list handling—which Dijkstra had made a special process—could be integrated into the regular data structure, requiring no special handling.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- At DEC (Digital Equipment Corporation), which Lamport joined in 1985, they had built one of the first distributed operating systems with all computers on an Ethernet network sharing common storage, maintaining consistency via algorithms rather than explicit code.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- When Lamport first presented the Paxos paper at a lecture dressed as an archaeologist (playing up the fictional 'ancient Greek parliament' framing), the audience may have enjoyed the presentation, but they did not understand the algorithm or its significance.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Much research in distributed systems theory attempts to use partial orderings and behavioral proofs, which is not the practical way to build systems; the method that reliably works is invariance proofs, though there are exceptions like the bakery algorithm where partial orderings are useful.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- An algorithm is more abstract than a program—it can be implemented in any programming language, whereas a program is concrete code in a specific language; thinking in terms of algorithms rather than code is crucial for concurrent systems.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- When describing algorithms, Lamport talks about variables that can hold any integer, not just finite-precision integers—a deliberate abstraction that simplifies reasoning, not a complication; infinity was introduced into mathematics to simplify arithmetic, not complicate it.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport