A self-stabilizing protocol for pipelined PIF in tree networks
A self-stabilizing protocol for pipelined PIF in tree networks
复制标题
树状网络中管道式 PIF 的自稳定协议
DOI：
10.1109/icdcs.2002.1022255
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
T. Masuzawa
中科院分区：
文献类型：
--
作者：
Daisuke Kondou;Hideo Masuda;T. Masuzawa
自稳定是实现分布式系统容错的一个有前途的范例。即使从任何系统配置开始，自稳定协议也可以收敛到其预期行为，因此可以容忍任何类型和任意数量的瞬态故障。树形网络中的 PIF（带有反馈的信息传播）方案允许根进程将其信息广播到所有其他进程并收集它们的响应。许多分布式系统利用 PIF 方案作为基本通信方案。本文首先在树网络中形式化了管道式 PIF，并提出了管道式 PIF 的自稳定协议。该协议以管道方式将 PIF 应用于一系列信息。该协议的稳定时间为 O(h)（其中 h 是树形网络的高度）。稳定后，它在 O(h) 异步轮次中完成每个 PIF，并且吞吐量为 O(1)。此外，该协议实现了故障遏制：对于完整的二叉树网络，其从 1 故障配置到稳定的预期时间为 O(1)。
Self-stabilization is a promising paradigm for achieving fault-tolerance of distributed systems. A self-stabilizing protocol can converge to its intended behavior even when it starts from any system configuration, and, thus, can tolerate any type and any number of transient faults. The PIF (propagation of information with feedback) scheme in a tree network allows the root process to broadcast its information to all other processes and to collect their responses. Many distributed systems utilize the PIF scheme as a fundamental communication scheme. This paper first formalizes the pipelined PIF in tree networks, and proposes a self-stabilizing protocol for the pipelined PIF. The protocol applies the PIF to a sequence of information in a pipelined fashion. The protocol has stabilizing time of O(h) (where h is the height of the tree network). After stabilization, it completes each PIF in O(h) asynchronous rounds and has throughput of O(1). Moreover, the protocol achieves fault-containment: for a complete binary tree network, its expected stabilizing time from 1-faulty configurations is O(1).