Self-stabilizing algorithms for synchronous unidirectional rings

Abstract

In this work we investigate the notion of built-in fault-tolerant (i.e. self-stabilizing) computations on a synchronous uniform unidirectional ring 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′ which runs on the synchronous unidirectional ring. P′ requires O(SLE(n)+S(n)) space and has expected stabilization time O(TLE(P) + n2 + nT(n)), where S(n) (T(n)) is the space (time) performance of P and SLE(n) (TLE(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.