Tournament Algorithm
Tournament is an N-thread mutex built from a binary (or d-ary) tree of 2-thread algorithms (Dekker or Peterson). A thread starts at a leaf and climbs to the root; winning the root = entering the critical section.
Why a tree rather than Bakery?
Tree traversal is
O(lg N)contention points per thread instead of scanning all N tickets. Fairness is a compromise, not FCFS — but no livelock (each 2-thread node has no livelock) and no starvation (each node guarantees progress, so every thread eventually reaches the root). Cheap on memory too:(N − 1) · Mbits for a minimal binary tree.
Shape (from Taubenfeld-Buhr)
- Maximal tree:
⌈N/2⌉start (leaf) nodes,⌈lg N⌉levels. - Each node runs a 2-thread mutex algorithm.
- Path from leaf to root is fixed per thread ⇒ table-lookup possible using max or min tree.
Exit protocol must retract in reverse order
Warning
Otherwise there’s a race between retracting and newly released threads along the same tree path.
- T0 retracts at D1.
- T1 (right child) now moves from D1 to D4 unopposed, sets intent at D4 (left), proceeds to D6.
- T0 (left) retracts its intent at D4 set by T1.
- T2/T3 continue from D2, set intent at D4 (right), proceed to D6 — mutual exclusion violated.
Code sketch
_Task TournamentMax { // Taubenfeld-Buhr
struct Token { int intents[2], turn; };
static Token ** t; // triangular matrix
int depth, id;
void main() {
unsigned int lid;
for ( int i = 0; i < 1000; i += 1 ) {
lid = id;
for ( int lv = 0; lv < depth; lv += 1 ) { // entry protocol
binary_prologue( lid & 1, &t[lv][lid >> 1] );
lid >>= 1;
}
CriticalSection( id );
for ( int lv = depth - 1; lv >= 0; lv -= 1 ) { // exit in REVERSE
lid = id >> lv;
binary_epilogue( lid & 1, &t[lv][lid >> 1] );
}
}
}
};Properties
- No overall livelock (no node has livelock).
- No starvation (each node guarantees progress ⇒ every thread eventually reaches the root).
- Unbounded overtaking — nodes don’t synchronize, so a thread can be passed many times.
- RW-safety depends on the underlying 2-thread algorithm.