Service time optimal self-stabilizing token circulation protocol on anonymous undirectional rings
Service time optimal self-stabilizing token circulation protocol on anonymous undirectional rings
复制标题
匿名无向环上服务时间最优自稳定代币流通协议
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
C. Johnen
中科院分区：
文献类型：
--
作者：
C. Johnen
提出了一个单向匿名环上的自稳定令牌循环协议。该协议不需要处理器标识符或区分处理器（即，所有处理器执行相同的算法）。该协议是随机化和自稳定的，这意味着从任意配置开始（响应于修改存储器状态的任意扰动），它达到（概率为1）合法配置（即网络中只有一个令牌的配置）。所有以前的随机化自稳定令牌循环协议都设计用于在不公平的分布式加密器下工作，具有相同的缺点：一旦稳定，服务时间很慢（在最好的情况下，它由2N限制，其中N是环的大小）。一旦稳定下来，我们的协议提供了一个最佳的服务：经过N个计算步骤，每个处理器都获得了一次令牌。该协议可以在任意环形拓扑网络中实现公平的分布式互斥。
We present a self-stabilizing token circulation protocol on unidirectional anonymous rings. This protocol requires no processor identifiers or distinguished processor (i.e. all processors perform the same algorithm). The protocol is randomized and self-stabilizing, meaning that starting from an arbitrary configuration (in response to an arbitrary perturbation modifying the memory state), it reaches (with probability 1) a legitimate configuration (i.e. a configuration with only one token in the network). All previous randomized self-stabilizing token circulation protocols designed to work under unfair distributed schedulers have the same drawback: once stabilized, service time is slow (in the best case, it is bounded by 2N where N is the ring size). Once stabilized, our protocol provides an optimal service: after N computation steps, each processor has obtained the token once. The protocol can be used to implement fair distributed mutual exclusion in any ring topology network.