On a Space-Optimal Distributed Traversal Algorithm
On a Space-Optimal Distributed Traversal Algorithm
复制标题
一种空间最优分布式遍历算法
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
S. Tixeuil
遍历算法是通过检查图的所有顶点和边来探索图的系统过程。如果每条边都检查一次，那么遍历就是欧拉式的。我们为欧拉遍历问题提出了一个简单的确定性分布式算法，它是空间最优的：每个节点都有d个状态，其中d是节点的出站度，但在执行欧拉遍历之前可能需要O（m2）个消息交换，其中m是网络中边的总数。此外，我们的解决方案具有容错特性：(i)在算法执行期间交换的消息可能有其内容损坏，（ii）节点的初始状态可能是任意的。然后讨论了该算法在自稳定虚电路构造和直通路由中的应用。自稳定[8,9]保证系统最终满足其规格，而不管系统的初始配置如何。在直通路由方案中，消息在被完整接收之前必须由中间节点转发。我们提出用随机化的方法对我们的算法进行变换，使所得到的协议对于虚拟电路的构造规范是自稳定的。与之前的几种自稳定虚拟电路构建算法不同，我们的方法内存占用小，不需要中央预处理或标识符，并且与直通路由兼容。
A traversal algorithm is a systematic procedure for exploring a graph by examining all of its vertices and edges. A traversal is Eulerian if every edge is examined exactly once. We present a simple deterministic distributed algorithm for the Eulerian traversal problem that is space-optimal: each node has exactly d states, where d is the outgoing degree of the node, yet may require O(m2) message exchanges before it performs an Eulerian traversal, where m is the total number of edges in the network. In addition, our solution has failure tolerance properties: (i) messages that are exchanged may have their contents corrupted during the execution of the algorithm, and (ii) the initial state of the nodes may be arbitrary.Then we discuss applications of this algorithm in the context of self-stabilizing virtual circuit construction and cut-through routing. Self-stabilization [8,9] guarantees that a system eventually satisfies its specification, regardless of the initial configuration of the system. In the cutthrough routing scheme, a message must be forwarded by intermediate nodes before it has been received in its entirety. We propose a transformation of our algorithm by means of randomization so that the resulting protocol is self-stabilizing for the virtual circuit construction specification. Unlike several previous self-stabilizing virtual circuit construction algorithms, our approach has a small memory footprint, does not require central preprocessing or identifiers, and is compatible with cut-through routing.