Peterson’s Algorithm and Software-Only Mutual Exclusion
Peterson's 1981 two-process algorithm showed that mutual exclusion could be expressed with only ordinary shared variables—provided the memory model supplied the ordering guarantees the proof assumes.
Mutual exclusion was already a foundational concurrency problem by 1981
The critical-section problem asks asynchronous processes to share a resource while ensuring that only one process occupies the protected region at a time. Edsger Dijkstra’s 1965 note gave the problem one of its canonical formulations and demonstrated that careful shared-state protocols could coordinate independent processes without assuming one central scheduler.[2] In the following decade, algorithms such as Leslie Lamport’s bakery algorithm explored stronger properties such as fairness and tolerance of overlapping reads and writes.[3] The subject became famous partly because apparently simple solutions were surprisingly easy to get wrong.
The difficulty was proving progress as well as exclusion
A correct algorithm had to prevent simultaneous entry, avoid deadlock when both processes competed, and avoid permanently starving one participant. A program that merely looked symmetric was not enough.
Gary Peterson’s paper deliberately attacked the belief that the two-process problem required complicated code
Gary L. Peterson’s 1981 paper, “Myths About the Mutual Exclusion Problem,” presented what became the standard two-process Peterson algorithm. The paper was short and polemical: Peterson began from simpler but flawed protocols and combined their ideas into a compact solution using two intent flags plus a shared turn variable.[1] The result became memorable because it made a notoriously subtle synchronization problem fit into a few lines of pseudocode while retaining a proof that ordinary readers could follow.
Each process announces interest before yielding priority
In the familiar formulation, process i sets its own flag to show that it wants the critical section, then writes the identity of the other process into the turn variable. It waits only while the other process is interested and the shared turn still favors the other process. If both processes arrive nearly together, both flags may be true, but the final value written to turn breaks the tie. If only one process is interested, the waiting condition immediately permits it to enter.[1]
The two shared mechanisms solve different problems
The flags communicate intent; the turn variable resolves simultaneous contention. Neither mechanism alone is sufficient under all interleavings, which is why Peterson’s construction is more than a clever syntactic trick.
The algorithm’s proof depends on reasoning about impossible combinations of shared state
To prove mutual exclusion, suppose both processes were in their critical sections. Each must have passed its waiting condition. With both intent flags still true, each process could pass only if turn favored itself. But the shared turn variable cannot simultaneously favor both processes. That contradiction establishes exclusion. Progress follows from the fact that a contending process cannot keep the turn in its own favor against another process indefinitely: the last process to announce contention yields priority through the turn assignment.
Peterson simplified an older lineage rather than inventing mutual exclusion itself
The historical significance of the algorithm comes from its position in a sequence of increasingly understandable solutions. Dijkstra’s 1965 work established the shared-memory critical-section problem as a central concurrency question.[2] Lamport’s 1974 bakery algorithm showed how processes could choose numbered tickets and obtain mutual exclusion without relying on lower-level exclusion primitives.[3] A modern historical review places Peterson’s 1981 contribution in this lineage as the especially simple two-process solution for atomic read/write memory.[4]
Simplicity became a teaching advantage
Because every variable has a visible logical role, Peterson’s algorithm became a standard example for showing how interleavings, invariants and liveness arguments fit together.
The phrase software-only comes with a crucial memory-model assumption
Peterson’s algorithm does not require a hardware test-and-set instruction, but that does not mean it works under every possible hardware or compiler reordering. The proof assumes that reads and writes of the shared variables behave with sufficiently strong atomicity and ordering. Lamport’s 1979 definition of sequential consistency made this issue explicit by requiring that the result appear as some interleaving of all processors’ operations while preserving each processor’s program order.[5] Under weaker memory models, the writes to a flag and turn can become visible in surprising orders unless the implementation uses fences or language-level atomic operations.
Modern hardware changed how programmers should interpret the classic pseudocode
Contemporary compilers may reorder ordinary accesses, keep values in registers, or exploit the fact that unsynchronized data races are outside the guarantees of a language memory model. Processors may also buffer writes. Therefore, transcribing Peterson’s original variables as ordinary shared C or C++ integers is not a portable implementation strategy. The algorithm remains correct as a mathematical protocol under its stated memory assumptions, but a real program must express those assumptions through atomics and ordering constraints.
The lesson is about specifications, not nostalgia
A synchronization proof applies to a model. When a programming language or processor provides a weaker model, the implementation must restore the ordering relationships on which the proof depends.
Why Peterson’s algorithm belongs in the history of concurrency
Peterson’s algorithm matters because it made three ideas visible at once. First, mutual exclusion can be achieved from ordinary read/write communication under an appropriate shared-memory model. Second, very small concurrent programs can require nontrivial proofs because correctness depends on all possible interleavings. Third, the meaning of “ordinary memory” is itself a technical contract that later compiler and hardware optimizations forced programmers to examine more carefully.[1][5]
The algorithm therefore survived as more than an interview puzzle or classroom exercise. It is a compact historical bridge between early critical-section research and modern memory-model engineering. Its few lines of code are useful precisely because they make hidden assumptions discussable.
Peterson’s contribution was not to eliminate the complexity of concurrency. It relocated that complexity into a proof whose assumptions can be named. That is one of the enduring disciplines of concurrent programming: state the model, state the invariant, and never assume that source-code order automatically equals memory order.
Works Cited
- 01Gary L. Peterson — Myths About the Mutual Exclusion Problem zoo.cs.yale.edu
- 02
- 03
- 04Raynal — A Visit to Mutual Exclusion in Seven Dates sciencedirect.com
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead