There are n+1 processors named 0, 1, ..., n. Processor i has a counter C(i) that takes values in the range [0, n]. Its initial value is arbitrarily chosen from [0, n]. Processor 0 is said to be privileged if C(0) = C(n). Processor i, where i > 0, is said to be privileged if C(i) ≠ C(i-1). At successive clock ticks, exactly one out of possibly several privileged processors is arbitrarily chosen and its counter is updated as follows: If processor 0 is chosen, we set C(0) ← (C(0) + 1) mod (n+1). Otherwise, we set C(i) ← C(i-1). Prove that after a bounded number of clock ticks, exactly one processor will be privileged. And that this will continue to hold forever.

Heard from a fellow student at UC Berkeley in 1996. In a seminal paper Self Stabilizing Systems in spite of Distributed Control, E W Dijkstra spawned the area of "self-stabilization". His paper contains three non-trivial algorithms — without proofs! "The appreciation [of these results] is left as an exercise for the reader", wrote Dijkstra. He won the PODC Influential Paper Award in 2002 for this work.

A Simple Proof for O(n^2) Convergence of Dijkstra's Self-Stabilization Protocol by G S Manku, 1996 (unpublished).

Analyze the other two protocols in Dijkstra's paper.