Self-stabilizing unidirectional network algorithms by power supply

Power supply, a surprisingly simple and new general paradigm for the develo pment of self-stabilizing algorithms in different models, is introduced. Th e paradigm is exemplified by developing simple and efficient self-stabilizi ng algorithms for leader election and either breadth-first search or depth- first search spanning-tree constructions, in strongly connected unidirectio nal and bidirectional dynamic networks (synchronous and asynchronous). The different algorithms stabilize in O(n) time in both synchronous and asynchr onous networks without assuming any knowledge of the network topology or si ze, where n is the total number of nodes. Following the leader election alg orithms, we present a generic self-stabilizing spanning tree and/or leader election algorithm that produces a whole spectrum of new and efficient algo rithms for these problems. Two variations that produce either a rooted dept h-first search tree or a rooted breadth-first search tree are presented.