THE FOLD / BOSS / THE GATEKEEPER / THE BAKERY ALGORITHM
THE BAKERY ALGORITHM
take a number; no atomic instruction required
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Lamport, 1974. Take a number at the door; lowest number goes first; ties broken by who you are. No atomic instruction anywhere — it is correct even if a read that overlaps a write returns garbage.
LIT verified live. breadth-first search over the entire reachable state space of two threads gives 77 states, of which 14 have a thread in the critical section and 0 have both — mutual exclusion, exhausted rather than argued. The fairness half is measured on one arrival stream served two ways: under the bakery discipline 0 of 10,000 entrants are overtaken by someone who arrived later, while a test-and-set lock choosing among the 8 waiting threads overtakes 8,715 of them. The price is on the counter: after 10,000 entries the ticket number is 10,000, and it never resets.
LIT verified live. breadth-first search over the entire reachable state space of two threads gives 77 states, of which 14 have a thread in the critical section and 0 have both — mutual exclusion, exhausted rather than argued. The fairness half is measured on one arrival stream served two ways: under the bakery discipline 0 of 10,000 entrants are overtaken by someone who arrived later, while a test-and-set lock choosing among the 8 waiting threads overtakes 8,715 of them. The price is on the counter: after 10,000 entries the ticket number is 10,000, and it never resets.
2 HOW IT WAS WEAVED · AI + HUMAN
Leslie Lamport’s bakery algorithm (1974) is the classic result that mutual exclusion needs no atomic hardware.
AVAN (AI) checked mutual exclusion by model checking rather than by reading the proof, and measured fairness rather than repeating the word. The fairness figure was nearly a fabrication: the first version simply set the bakery’s overtake count to zero on the grounds that FIFO is FIFO. It was rebuilt to run both disciplines over the same arrival stream through the same counter, so the 0 is a measurement and not an assumption. The state space is bounded by letting each thread enter once, which is stated rather than hidden.
AVAN (AI) checked mutual exclusion by model checking rather than by reading the proof, and measured fairness rather than repeating the word. The fairness figure was nearly a fabrication: the first version simply set the bakery’s overtake count to zero on the grounds that FIFO is FIFO. It was rebuilt to run both disciplines over the same arrival stream through the same counter, so the 0 is a measurement and not an assumption. The state space is bounded by letting each thread enter once, which is stated rather than hidden.
3 ONE DIMENSION
77 states. Fourteen have someone inside. None have two.
4 TWO DIMENSIONS · INTERACTIVE
Step the two threads and try to get both into the room.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that the bakery needs no special hardware. The inverse is that it replaces one atomic instruction with an unbounded counter and 2N shared variables that every thread must read on every entry. Lamport did not remove the cost of agreement; he moved it from a bus lock into 16 shared words and a number that grows forever. Read backwards, ‘no atomic operation required’ is a claim about the instruction set, not about the work — and the work turns out to scale with how many of you there are, which is exactly what the lock instruction was hiding.
LIT breadth-first search over the entire reachable state space of two threads gives 77 states, of which 14 have a thread in the critical section and 0 have both - mutual exclusion exhausted rather than argued; and on one arrival stream served two ways, the bakery discipline lets 0 of 10,000 entrants be overtaken by a later arrival while a test-and-set lock choosing among the 8 waiting threads overtakes 8,715 - the price being a ticket counter that reaches 10,000 and never resets, plus 16 shared words
FIG Leslie Lamport's bakery algorithm (1974) is the classic result that mutual exclusion needs no atomic hardware. AVAN checked mutual exclusion by model checking rather than by reading the proof, and measured fairness rather than repeating the word. The fairness figure was nearly a fabrication: the first version simply SET the bakery's overtake count to zero on the grounds that FIFO is FIFO. It was rebuilt to run both disciplines over the same arrival stream through the same counter, so the 0 is a measurement. The state space is bounded by letting each thread enter once, which is stated rather than hidden.
FIG Leslie Lamport's bakery algorithm (1974) is the classic result that mutual exclusion needs no atomic hardware. AVAN checked mutual exclusion by model checking rather than by reading the proof, and measured fairness rather than repeating the word. The fairness figure was nearly a fabrication: the first version simply SET the bakery's overtake count to zero on the grounds that FIFO is FIFO. It was rebuilt to run both disciplines over the same arrival stream through the same counter, so the 0 is a measurement. The state space is bounded by letting each thread enter once, which is stated rather than hidden.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN