1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ It would help if you explained the algorithm and what it is trying to accomplish. $\endgroup$ – Yuval Filmus Nov 20 '15 at 15:38
  • $\begingroup$ 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 $\endgroup$ – Marcel Nov 20 '15 at 15:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.