## The Black-White Bakery Algorithm

### Author

- Gadi Taubenfeld, The Interdisciplinary Center, Israel

### Abstract

A mutual exclusion algorithm is presented that has four desired
properties: (1) it satisfies FIFO fairness, (2) it satisfies
local-spinning, (3) it is adaptive, and (4) it uses finite number of
bounded size atomic registers. No previously published algorithm
satisfies all these properties. In fact, it is the first algorithm
(using only atomic registers) which satisfies both FIFO and
local-spinning, and it is the first bounded space algorithm which
satisfies both FIFO and adaptivity.
All the algorithms presented are based on Lamport's famous Bakery
algorithm, which satisfies FIFO, but uses unbounded size registers.
Using only one additional shared bit, we bound the amount of space
required by the Bakery algorithm. Then, in a sequence of steps which
preserve simplicity and elegance, we modify the new algorithm so that
it is also adaptive to point contention and satisfies local-spinning.