SELF-STABILIZING DISTRIBUTED SORTING IN TREE NETWORKS
SELF-STABILIZING DISTRIBUTED SORTING IN TREE NETWORKS
复制标题
树网络中的自稳定分布式排序
DOI：
10.1080/01495730108935263
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
A. Datta;S. Tixeuil
本文提出了一种树网络的自稳定分布式排序算法。分布式排序问题可以非正式地描述如下：节点合作以达到全局配置，其中每个节点根据其标识符被分配一个特定的最终值，该最终值取自分布在所有节点上的一组输入值。输入值可能会随时间改变。在我们的解决方案中，系统在输入值稳定且故障停止后在有限时间内达到最终配置。使用 Dijkstra 的自稳定范式实现了容错和对不断变化的输入的适应性。无论初始系统状态如何，自稳定算法都将在有限时间内收敛到一组合法状态，而不需要显式异常处理程序或向后恢复。我们的解决方案基于沿着树边缘的连续广播和确认，以实现系统中进程之间的同步。它的时间复杂度为 0(n ×h)，内存需求仅为 0(log(n) × )，其中 h 是树的度，h 是树的高度。
This paper presents a self-stabilizing distributed sorting algorithm for tree networks. The distributed sorting problem can be informally described as follows: Nodes cooperate to reach a global configuration where every node, depending on its identifier, is assigned a specific final value taken from a set of input values distributed across all nodes. The input values may change in time. In our solution, the system reaches its final configuration in a finite time after the input values are stable and the faults cease. The fault-tolerance and the adaptivity to changing input is achieved using Dijkstra's paradigm of self-stabilization. A self-stabilizing algorithm, regardless of the initial system state, will converge in finite time to a set of legitimate states without the need for explicit exception handlers or backward recovery. Our solution is based on a continuous broadcast with acknowledgment along the tree edges to achieve the synchronization among processes in the system. It has 0(n ×h) time complexity and only 0(log(n) × ) memory requirement where h is the degree of the tree and h is the height of the tree.