Bounded service time and memory space optimal self-stabilizing token circulation protocol on unidirectional rings

Summary form only given. Robustness is one of the most important requirements of modern distributed systems. Various types of faults are likely to occur at various parts of the system. The concept of self-stabilization is the most general technique to design a system to tolerate arbitrary transient faults. A self-stabilizing system, regardless of the initial states of the processors and initial messages in the links, is guaranteed to converge to the intended behavior in finite time. We present a self-stabilizing token circulation protocol on unidirectional anonymous rings. This protocol does not require processor identifiers, no distinguished processor (i.e. all processors perform the same code). The algorithm can deal with any kind of schedules even unfair ones. Our protocol is the first one having the two major advantages : the duration of a token circulation is bounded and the protocol is optimal in memory space. The memory space required by our protocol on each processor is 0(lg(M_N)), M_N being the smallest non divisor of ring size. Our protocol is a randomized self-stabilizing, meaning that starting from an arbitrary configuration (in response to an arbitrary perturbation modifying the memory state), it reaches (with probability 1) a legitimate configuration (i.e. a configuration with only one token in the network). Once the system is stabilized, the circulation of the sole token is 1-fair (i.e. in every round, every processor obtains the token one time).