THE FOLD / BOSS / THE GAUNTLET / THE DINING PHILOSOPHERS
THE DINING PHILOSOPHERS
everyone correct, in the same way, at the same time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Five philosophers, five forks, and a rule so reasonable it is fatal: pick up your left fork, then your right. Everyone can obey it simultaneously, and if they do, nobody eats again.
LIT verified live. breadth-first search over the entire reachable state space of the symmetric protocol finds 82 states, of which exactly 1 has no successor at all — the state
LIT verified live. breadth-first search over the entire reachable state space of the symmetric protocol finds 82 states, of which exactly 1 has no successor at all — the state
11111, every philosopher holding a left fork and waiting on a right that will never be released. Reverse the order for a single philosopher and the search finds 70 reachable states and 0 deadlocks. One asymmetry, applied to one of five, removes the whole failure — and it also removes 12 reachable states, which is what the fix costs.2 HOW IT WAS WEAVED · AI + HUMAN
The dining philosophers are Dijkstra’s (1965); the asymmetric fix — make one philosopher left-handed — is the standard remedy, as is the resource hierarchy it generalises to.
AVAN (AI) searched the state graph rather than reasoning about the cycle, so the deadlock is not a story about it but an enumerated fact: 1 terminal state, and it is identified by name. The 82 → 70 is the part that arguments usually omit — the fix does not merely delete the bad state, it deletes twelve reachable configurations, because forbidding a symmetry forbids more than the one arrangement you were afraid of.
AVAN (AI) searched the state graph rather than reasoning about the cycle, so the deadlock is not a story about it but an enumerated fact: 1 terminal state, and it is identified by name. The 82 → 70 is the part that arguments usually omit — the fix does not merely delete the bad state, it deletes twelve reachable configurations, because forbidding a symmetry forbids more than the one arrangement you were afraid of.
3 ONE DIMENSION
82 states. Exactly one of them has no way out.
4 TWO DIMENSIONS · INTERACTIVE
Pick up forks yourself and try to reach the trap.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that breaking the symmetry breaks the deadlock. The inverse is that the deadlock was not caused by scarcity but by everyone being correct in the same way at the same time. Every philosopher followed a locally sound rule; the failure is a property of the set, invisible in any one of them. Read backwards, a protocol that is safe for each participant can be lethal for all of them, and the only cure is to make somebody behave differently for no reason they could justify locally — correctness bought by mandating an inconsistency.
LIT breadth-first search over the entire reachable state space of the symmetric protocol finds 82 states of which exactly 1 has no successor at all - the state 11111, every philosopher holding a left fork and waiting on a right that is never released - while reversing the order for a single philosopher gives 70 reachable states and 0 deadlocks, so one asymmetry applied to one of five removes the whole failure and also removes 12 reachable states, which is what the fix costs
FIG The dining philosophers are Dijkstra's (1965); the asymmetric fix is the standard remedy. AVAN searched the state graph rather than reasoning about the cycle, so the deadlock is an enumerated fact with a name rather than a story. The 82 to 70 is the part arguments usually omit - the fix does not merely delete the bad state, it deletes twelve reachable configurations, because forbidding a symmetry forbids more than the one arrangement you were afraid of.
FIG The dining philosophers are Dijkstra's (1965); the asymmetric fix is the standard remedy. AVAN searched the state graph rather than reasoning about the cycle, so the deadlock is an enumerated fact with a name rather than a story. The 82 to 70 is the part arguments usually omit - the fix does not merely delete the bad state, it deletes twelve reachable configurations, because forbidding a symmetry forbids more than the one arrangement you were afraid of.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GAUNTLET · David Lee Wise (ROOT0), with AVAN