Memory space requirements for self-stabilizing leader election protocols
Memory space requirements for self-stabilizing leader election protocols
复制标题
自稳定领导者选举协议的内存空间要求
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
C. Johnen
中科院分区：
文献类型：
--
作者：
J. Beauquier;M. Potop;C. Johnen
研究了自稳定领袖选举(SSLE)协议的存储需求。我们主要对两类系统感兴趣：匿名系统和基于身份的系统。我们考虑两类协议：确定性协议和随机化协议。我们证明了单向匿名环上的SSLE协议(即使该协议是随机的)需要存储空间的非常数下界。我们证明了，如果在基于id的系统上存在一个解决问题的确定性协议，其中处理器存储空间是常量的，并且id值是无界的，那么在使用恒定存储空间的匿名系统上存在一个解决相同问题的确定性协议。因此，匿名环上的不可能性结果(即，人们可以在集中式守护程序下仅在素数环上设计确定性SSLE协议)可以扩展到那些类型的基于ID的环。然而，在基于ID的单向环上设计需要恒定存储空间的静默和确定性SSLE协议是可能的，其中ID值是有界的。我们提出了这样一个协议。在任意大小的匿名和单向环上，我们还提出了一个随机SSLE协议和一个不公平的分布式守护进程下的令牌循环协议。我们给出了存储空间需求的下界，证明了这些协议是空间最优的。平均而言，所需的内存空间是恒定的。关键词：自我稳定、领导人选举、互斥、可决断性、记忆空间需求。
We study the memory requirements of self-stabilizing leader election (SSLE) protocols. We are mainly interested in two types of systems: anonymous systems and id-based systems. We consider two classes of protocols: deterministic ones and randomized ones. We prove that a non-constant lower bound on the memory space is required by a SSLE protocol on unidirectional, anonymous rings (even if the protocol is randomized). We show that, if there is a deterministic protocol solving a problem on id-based systems where the processor memory space is constant and the id-values are not bounded then there is a deterministic protocol on anonymous systems using constant memory space that solves the same problem. Thus impossibility results on anonymous rings (i.e. one may design a deterministic SSLE protocol, only on prime size rings, under a centralized daemon) can be extended to those kinds of id-based rings. Nevertheless, it is possible to design a silent and deterministic SSLE protocol requiring constant memory space on unidirectional, id-based rings where the id-values are bounded. We present such a protocol. We also present a randomized SSLE protocol and a token circulation protocol under an unfair, distributed daemon on anonymous and unidirectional rings of any size. We give a lower bound on memory space requirement proving that these protocols are space optimal. The memory space required is constant on average. Keyword: self-stabilization, leader election, mutual exclusion, decidability, memory space requirement.