The Black-White Bakery Algorithm



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.