Cairn
algorithms · concurrency · O(1) time and space, two-process mutual exclusion

↩ back to Concurrency

Dekker's Algorithm

One of this site's other Concurrency entries is actually the second draft of this page's own idea. Peterson's algorithm is a 1981 simplification; the algorithm it simplified — attributed by Edsger Dijkstra to Th. J. Dekker and published in 1965 — is the first known solution to two-process mutual exclusion using nothing but ordinary shared-memory reads and writes. It solves exactly the same problem Peterson's algorithm does, with the same two ingredients (a flag per process, a shared turn), but it reaches the guarantee by a different, more roundabout route: instead of one clean check that either lets a process straight through or makes it wait, Dekker's algorithm has a process back off its own flag when it isn't its turn, then wait, then re-raise the flag and check again from the start. Peterson's whole contribution was noticing that the same guarantee follows from a single combined check — no backing off required. Seeing the more complicated original makes clear exactly what that simplification bought.

Same measure-don't-assume discipline as this site's other ten Concurrency pages: every claim below — that the full algorithm holds, and exactly how two tempting shortcuts break it — comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.

Try it

Pick a variant and how many times each process tries to enter, then either step through by hand — Step P0 / Step P1 run exactly one pending action for that process, or report why it can't act right now — or press Explore all schedules to search every reachable interleaving at once. Try No backoff with 1 attempt each first — it's the fastest way to see why Dekker bothered with turn at all. Then try No re-raise with P0 set to 2 attempts and P1 set to 1; the first attempt each looks completely fine, and the bug only shows up once P0 gets a second chance to enter.

Pick a variant and attempt counts, then step each process by hand.

Why it works

Two shared variables, same as Peterson's algorithm: flag[i] ("I want in") and turn (whoever it names gets priority if both want in). Entering for process i (with j the other process) runs this loop: set flag[i] = true; then while flag[j] is true, check turn — if turn === j, it genuinely isn't i's turn, so i backs off (flag[i] = false), waits until turn changes away from j, then raises flag[i] = true again and goes back to re-checking flag[j] from the top; if turn === i instead, i just keeps busy-waiting on flag[j] alone, because this round it has priority. The loop ends, and i enters, the moment it finds flag[j] false. Exiting sets turn = j (hand priority to the other process for next time) and clears flag[i] = false.

The backoff step is the one piece Peterson's algorithm doesn't need, and it exists to solve a real problem: without it, two processes that both set their flag true before either checks the other's would just spin on each other's flag forever (see Pitfalls below — this is exactly what happens with turn removed). Backing off breaks that deadlock by making one of the two processes voluntarily lower its own flag and wait its turn, so the other's check of that flag can eventually see it drop to false.

Mutual exclusion holds because of one invariant: whenever process i is about to re-check flag[j] from a position of actually trying to enter, its own flag[i] is true — it was either just set true at the very start of this attempt, or just re-raised after a backoff, and nothing in between ever lowers it again before the next check. That includes the instant i actually enters: the check that lets it through only ever fires from that same position, so flag[i] is still true at the moment of entry, and stays true (nothing in the critical section touches it) until i exits. Now suppose, for contradiction, both processes were in the critical section at once. Both flags are therefore true throughout that overlap. But process 1 only entered after its own check found flag[0] false — and if process 0 was already inside (continuously, by the invariant, with its flag true the whole time), that check could never have found flag[0] false in the first place. Contradiction either way round. The No re-raise variant below exists precisely to show what happens when the invariant's premise — "flag[i] is true every time i checks" — is the one thing that gets dropped.

Reference implementation

Same ground rules as five of this site's other ten Concurrency pages: ordinary reads and writes to shared memory, interleaved arbitrarily by the scheduler, no compare-and-swap or other special hardware operation. (The other five — the Treiber Stack, the Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List — all lean on hardware compare-and-swap somewhere in their own design, the primitive these five pages deliberately do without.)

const flag = [false, false];
let turn = 0;

function enter(i) {
  const j = 1 - i;
  flag[i] = true;
  while (flag[j]) {
    if (turn === j) {
      flag[i] = false;        // back off: let the other go first
      while (turn === j) {
        // busy-wait: it's still not my turn
      }
      flag[i] = true;          // re-raise before checking flag[j] again
    }
    // else turn === i: keep busy-waiting on flag[j] alone
  }
  // critical section
}

function exit(i) {
  turn = 1 - i;
  flag[i] = false;
}

The demo above runs this exact shape as a step-by-step state machine — the initial flag[i] = true, the combined flag[j]/turn check, the backoff write, the wait-for-turn check, the re-raise, entry, and exit are each their own click — not a simplified stand-in for it. Checking flag[j] and turn together is modeled as one read-only step (nothing is written in between the two reads in the real code either), but every write — lowering the flag to back off, raising it again, entering, exiting — is its own separate, independently interleavable move.

Pitfalls

Removing the backoff (and turn with it) trades the race for the exact deadlock the backoff exists to prevent. Drop turn entirely and Dekker's algorithm reduces to the most obvious thing to try first: flag[i] = true; spin while flag[j]; enter; flag[i] = false. It still never lets both processes into the critical section together — exhaustively confirmed, 0 violations at every configuration tried, up to 91 reachable states at 3 attempts each — but it deadlocks outright, by the shortest possible path: P0 sets flag[0] = true, then P1 sets flag[1] = true. Now both flags are true, both processes are spinning on the other's flag, and neither will ever change again, because clearing either one requires passing the very spin that's now stuck. Two ordinary-looking clicks, in either order, and it's wedged forever — the identical failure shape as Peterson's own flag-only variant, which makes sense: with no turn to break the tie, this is Peterson's flag-only variant, just arrived at from the opposite direction (a historical first attempt, rather than a simplification of something that already worked). At 3 attempts each, the number of distinct stuck states climbs to 9. As with Peterson's version, a process that never asks for the resource can never contribute to this — 1 or 3 attempts for just one side, 0 for the other, finds 0 stuck states.

Forgetting to re-raise the flag after backing off doesn't just risk a liveness bug — it breaks mutual exclusion itself. The backoff step temporarily sets flag[i] = false, and the real algorithm always sets it back to true before re-checking flag[j]. Skip that one re-raise — resume checking flag[j] directly once turn changes, without ever setting flag[i] true again — and the central invariant from Why it works stops holding: a process can now reach, and even enter, the critical section with its own flag still reading false. Exhaustively confirmed at 1 attempt each: 0 violations, 21 reachable states — the bug can't trigger on the very first attempt, because the backoff path itself is only reachable after real contention, and nothing yet has had a reason to re-enter. Give P0 a second attempt (2 attempts for P0, 1 for P1): 49 reachable states, exactly 1 violation, reached by the shortest path in 9 moves. The shape of it: P0 enters and exits normally first, handing turn to P1. P1 then raises its flag, sees P0's flag still true, and backs off — but by the time turn comes back around to P1, it resumes without re-raising, so it enters the critical section with flag[1] sitting at false. P0, starting its second attempt, checks flag[1], sees false — because the re-raise that should have made it true never happened — and enters too, right alongside P1. Both inside at once, each having made a locally correct-looking decision off a flag that was lying about the other's real state. At 3 attempts each, the violation count climbs to 10.

variantattempts (P0, P1)reachable statesviolationsstuck states
Dekker's (full)1, 11900
Dekker's (full)3, 319700
No backoff1, 11501
No backoff3, 39109
No re-raise1, 12100
No re-raise2, 14910
No re-raise3, 3267100

This page's two broken variants land on opposite sides of a line Peterson's and Lamport's bakery algorithm's own broken variants also draw, between them: removing turn altogether (here, and in Peterson's flag-only variant) only ever costs liveness — deadlock or starvation, never a safety violation. Breaking the piece that's supposed to keep a process's own flag trustworthy (here, and in the bakery algorithm's two broken variants) costs safety itself. No re-raise is the first instance of that second kind of bug on a two-process page — the turn-handling logic survives completely intact; what breaks is a single process's own flag no longer meaning what the rest of the algorithm assumes it means.

Complexity

Time: O(1) per entry/exit with no contention — same bound as Peterson's algorithm, since the no-contention path is just flag[i] = true, one false check of flag[j], enter. Under contention, the backoff loop adds real work Peterson's algorithm never needs: a process can lower and re-raise its own flag multiple times before finally getting in, where Peterson's single combined check never requires revisiting a write it already made. Bounded waiting still holds — a process backs off at most while it's genuinely not its turn, and turn changes hands every single exit, so the wait is bounded by one full pass of the other process through the critical section, same guarantee Peterson's algorithm gives, just reached with more steps along the way. Space: O(1) — two shared variables, identical footprint to Peterson's algorithm.

The real cost Dekker's algorithm pays versus Peterson's isn't asymptotic — both are O(1) — it's the number of distinct reads and writes a real contended run performs, and the reachable-state counts above are a direct proxy for that: the full algorithm already needs 19 states to cover 1 attempt each where Peterson's needs 26 for the same configuration, but Dekker's own backoff/re-raise cycle can repeat an arbitrary number of times under sustained contention before either side wins, while Peterson's combined check resolves the same contention in one step every time. That's exactly the gap Peterson's algorithm closed in 1981: same two primitives, same guarantee, same asymptotic cost, fewer moving parts to get wrong — this page's No re-raise variant is a demonstration of one of the extra parts. Lamport's bakery algorithm later solved a different problem neither two-process algorithm attempts: generalizing the same shared-state idea to any fixed number of processes n, at O(n) cost per entry rather than O(1). See Choosing a Mutual Exclusion Algorithm for all three side by side — including the real publication order, which runs differently than "later" suggests once Peterson's algorithm is back in the picture.