Self-Stabilizing Unidirectional Network Algorithms by Power-Supply (Extended Abstract).
Yehuda Afek, Anat Bremler-Barr · 1997
) Yehuda Afek Anat Bremler Abstract Power-supply, a surprisingly simple and new general paradigm for the development of self-stabilizing algorithms in different models, is introduced. The paradigm is exemplified by developing simple and efficient selfstabilizing algorithms for leader election and either BFS or DFS spanning tree constructions, in stronglyconnected unidirectional and bi-directional dynamic networks (synchronous and asynchronous). The different algorithms stabilize in O(n) time in both synchronous and asynchronous networks without assuming any knowledge about the network topology or size, where n is the total number of nodes. Following the leader election algorithms we present a generic selfstabilizing spanning tree and/or leader election algorithm that produces a whole spectrum of new and efficient algorithms for these problems. Two variations that produce either a rooted Depth First Search tree or a rooted Breadth First Search tree are presented. 1 Introduction A ...