Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings
Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings
复制标题
环上任意调度器下的随机自稳定和空间最优领导者选举
作者：
J. Beauquier;M. Potop;C. Johnen
我们在任意规模的匿名单向环上提出了一个随机自稳定领导者选举协议和一个随机自稳定令牌循环协议，该协议在任意调度器下运行。这些协议是空间最优的。我们也给出了这些协议的形式和完整的证明。为此，我们开发了一个完整的模型，概率自稳定的分布式系统，明确分离的非确定性行为的调度协议的随机行为。这个框架包括所有必要的工具来证明一个随机分布系统的自稳定性：定义的概率空间和定义的自稳定的随机协议。我们还提出了一种新的技术调度管理通过自稳定的协议组成（交叉组成）。粗略地说，我们强制所有计算在任何调度器下都具有公平性，即使是在不公平的调度器下。
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.