# Why do we need $k \geq n$ in Dijkstra's token ring self-stabilizing system?

Let's say I have a ring with four nodes $n=\{0;1;2;3\}$ and three possible states $k=\{0;1;2\}$. A transient failure happens and the system ends up in an illegal state.

I know from the restriction ($k \geq n$) that there should be an execution that makes the system stay in its illegal state indefinitely, but for all the executions I try in my head and on paper, it still stabilises at some point. Could you give me an execution where it loops always back into its illegal state?

• It would help if you explained the algorithm and what it is trying to accomplish. – Yuval Filmus Nov 20 '15 at 15:38
• It is Dijkstra's Token Ring Self-Stabilizing System, a well-known algorithm for self-stabilization and can be found in any standard textbook on Distributed Systems – Marcel Nov 20 '15 at 15:51

Here is how to solve this for your particular $n$ and $k$. Your system has $k^n = 81$ possible states. You can describe the evolution of the system as a directed graph: there is an edge $s_1 \to s_2$ if state $s_1$ evolves in one step to state $s_2$. Some states are legal, some are illegal. You want to find an illegal state $s$ from which no legal state is reachable. This is a question that can be solved using a graph traversal algorithm such as DFS.

Once you find such a state, you can try to generalize the construction to other values of $n$ and $k$. Other simulations (with other values of $n$ and $k$) could be helpful here.