Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings |
| |
Authors: | Joffroy Beauquier Maria Gradinariu Colette Johnen |
| |
Affiliation: | (1) LRI, Univ. Paris-Sud, CNRS, Bat 490, 91405 Orsay, France;(2) LIP6, Univ. Paris 6, CNRS, INRIA, Paris, France |
| |
Abstract: | We present a randomized self-stabilizing leader election protocol and a randomized self-stabilizing token circulation protocol
under an arbitrary scheduler on anonymous and unidirectional rings of any size. These protocols are space optimal. We also
give a formal and complete proof of these protocols. To this end, we develop a complete model for probabilistic self-stabilizing
distributed systems which clearly separates the non deterministic behavior of the scheduler from the randomized behavior of
the protocol. This framework includes all the necessary tools for proving the self- stabilization of a randomized distributed
system: definition of a probabilistic space and definition of the self-stabilization of a randomized protocol. We also propose
a new technique of scheduler management through a self-stabilizing protocol composition (cross-over composition). Roughly speaking, we force all computations to have a fairness property under any scheduler, even under an unfair one.
This work was done while Maria Gradinariu was working at LRI, Univ. Paris-Sud, CNRS. |
| |
Keywords: | Self-stabilization Randomized protocol Protocol composition Scheduler Leader election |
本文献已被 SpringerLink 等数据库收录! |
|