White = not yet reached (candidate garbage); gray = reached but children not scanned; black = reached and fully scanned. The invariant: no black object points directly to a white one. Maintaining it (with write barriers) lets the collector run interleaved with the program that keeps mutating the heap — the abstraction under every modern incremental / concurrent GC.
THE TECHNIQUE gray to black, greying white children
Roots start gray. Repeatedly take a gray object, scan it (paint its white children gray), and paint it black. When no gray remains, every white object is unreachable — garbage. The invariant “no black → white” is what makes it safe to pause and resume while the program runs. Below: the sweep to a fixpoint, with the invariant checked. live demo
HISTORY & CREDIT five authors; Steele was concurrent first
“Dijkstra invented concurrent / tri-color GC” — alone no; the paper has five authors, and Steele published concurrent GC in 1975, three years earlier. cited
1975 · Guy Steele — the first published concurrent collector (semaphores + marking; not yet the color scheme). Dijkstra (EWD 492) poses the on-the-fly problem the same year. 1978 · Dijkstra, Lamport, Martin, Scholten & Steffens (CACM) — the white/gray/black formulation, the strong invariant, and a proof. The colors are genuinely theirs. 1984 · Ben-Ari gives a much simpler correctness proof (effectively two colors). 1990 / 1992 · the snapshot / deletion write barrier is Yuasa (shade the old referent), NOT Dijkstra’s insertion barrier (shade the new referent); Wilson names the “tricolour abstraction.”
Every production concurrent collector (Go, Java G1/ZGC/Shenandoah, .NET) is this 1978 invariant plus a choice of barrier. DLMSS, 1978
RECOMMEND FOR I-13 a color array; fixpoint; check the invariant
Colors are an f64 array (0/1/2); the sweep is a fixpoint; the invariant is one pass — and it holds:
$ i13 run tri.i13 # root {0}; 0->1->2 reachable; garbage 3->4, plus 5
final colors: black {0,1,2}=7 white/garbage {3,4,5}=56 gray {} at fixpoint
invariant 'no black -> white': 0 violations -> HOLDS
Recommend:nothing new — color is an f64 array (0 white / 1 gray / 2 black); the sweep finds a gray node, greys its white children (value-semantic update), blackens it, and recurses to a fixpoint; a final pass checks no black object has a white child (verified black {0,1,2}, garbage {3,4,5}, 0 violations). The tri-color invariant is the corpus’s kind of law — a property preserved through every step. Note: it completes the GC triad with mark-sweep (139, stop-the-world two-color) and Cheney (140, copying): tri-color is what makes marking incremental. A real concurrent heap needs write barriers on a node arena (PS-015); the corpus grounds the marking + the invariant on a color array.