Solution of a Problem in Concurrent Programming Control
đź“ś Abstract
A number of mainly independent sequential-cyclic processes with restricted means of communication with each other can be made in such a way that at any moment one and only one of them is engaged in the "critical section" of its cycle.
✨ Summary
The paper presents an early solution to the mutual-exclusion problem for multiple cyclic processes communicating through a shared store. Its algorithm uses per-process Boolean variables and a shared integer to ensure that no two processes simultaneously enter their critical sections, while also preventing indefinite “after you” blocking under highly variable process speeds. The paper explicitly requires symmetry, independence from relative process speeds, tolerance of halted processes outside their critical sections, and progress when several processes contend.
The work became a foundational reference point for subsequent mutual-exclusion research. Leslie Lamport identifies Dijkstra’s problem and solution as the starting point for the later bakery algorithm, and describes the study of that algorithm as an important source of his subsequent work on concurrency and distributed algorithms. (microsoft.com) Later research generalized bakery-style mutual exclusion to group mutual exclusion and developed bounded-register variants. (sciencedirect.com) The algorithm and its correctness have also continued to be used as examples in formal-verification research and educational treatments of concurrent systems. (lamport.azurewebsites.net)
The quick search found substantial research influence, but no specific industrial deployment directly attributable to this paper.