Lamport's bakery algorithm

Lamport's bakery algorithm is a mutual exclusion concurrent algorithm in which each participating process chooses a numbered ticket before entering a critical section. Process $i$ announces that it is choosing, sets its ticket to one more than the largest observed ticket, and finishes choosing. It then waits for each other process to finish choosing and for every smaller nonzero pair $(\text{ticket},\text{process identifier})$ to leave. Comparing identifiers breaks ties between equal tickets; setting one's ticket to zero announces departure.^[ref]

For example, simultaneous choices can give processes 2 and 5 the same ticket 7; pair $(7,2)$ precedes $(7,5)$. The choosing flag prevents treating an unfinished choice as an absent contender. Leslie Lamport's 1974 proof even permits an overlapping read to return an arbitrary value under the specified shared-register model. The mathematical model uses unbounded tickets; a bounded machine implementation must also address overflow and its memory model.^[ref]