Self-stabilizing algorithms for synchronous unidirectional rings
Alain J. Mayer, Rafail Ostrovsky, Moti M. Yung · Symposium on Discrete Algorithms · 1996
In this work we investigate the notion of built-in fault-tolerant (i.e. self-stabilizing) computations on a synchronous uniform unidirectionalring network. Our main result is a protocol-compiler that transforms any self-stabilizing protocol P for a (synchronous or asynchronous) bidirectional ring to a self-stabilizing protocol P{prime} which runs on the synchronous unidirectional ring. P{prime} requires O(S{sub LE} (n)+S(n)) space and has expected stabilization time O(T{sub LE}(n) + n{sup 2} + nT(n)), where S(n) (T(n)) is the space (time) performance of P and S{sub LE}(n) (T{sub LE}(n)) is the space (time) performance of a self-stabilizing leader-election protocol on a bidirectional ring. As subroutines, we also solve the problems of leader election and round-robin token management in our setting.