= Lamport's bakery algorithm
{c}
<Lamport's bakery algorithm> is a <mutual exclusion> <concurrent algorithm> in which each participating <process (computing)> 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.<A New Solution of Dijkstra's Concurrent Programming Problem by Leslie Lamport>[printed p.454, algorithm]{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>.<A New Solution of Dijkstra's Concurrent Programming Problem by Leslie Lamport>[pp.454–455, register assumptions and correctness]{ref}
Back to article page
