首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号