Uniform self-stabilizing ring orientation (Q2366560)

The paper deals with a class of uniform protocols that ensure the self- stabilization of ring type distributed systems. The self-stabilization means that a system with this property once started regains its consistency by itself, without any outside intervention. The authors discuss the problem of existence of uniform self-stabilizing protocols for ring orientation and show that the problem cannot be entirely solved by using deterministic protocols. In particular, they prove that there is not deterministic protocol for orienting rings of even size. Next, they present and prove the correctness of a randomized self-stabilizing protocol for ring orientation. The proposed protocol is composed of two levels, with a randomized lower level protocol. In the analysis it is assumed that all processors are randomized finite state machines that can communicate with their neighbours by using atomic registers. The authors find the expected stabilization time as well as the parallel complexity of the protocol, i.e., the maximal time over all possible initial configurations when every enables processor is activated.