Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Dijkstra's Self-Stabilization Protocol

Puzzle

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.

Source

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.

Solution

Followup

Analyze the other two protocols in Dijkstra's paper.

Using only a compass (and without a straight edge or a ruler), is it possible to identify (a) the midpoint of two points? (b) the center of a circle? (c) all four corners of a square, given two of them?

Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates.

15 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.