Published by MIT Press. Copyright 1997 Massachusetts Institute of Technology.

Your institution may already be a
subscriber to CJTCS. If not,
**please subscribe**
for legitimate access to all journal articles.

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 self-stabilizing algorithms for leader election and either
breadth-first search or depth-first search spanning-tree
constructions, in strongly connected unidirectional and bidirectional
dynamic networks (synchronous and asynchronous). The different
algorithms stabilize in *O(n)* time in both synchronous and
asynchronous networks without assuming any knowledge of the network
topology or size, where *n* is the total number of
nodes. Following the leader election algorithms, we present a generic
self-stabilizing 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.

- Preformatted versions of the article
**DVI:**Parts of Figures 5 and 6 are presented as encapsulated PostScript. With most WWW browsers, if you view the DVI file directly, you will not see that portion of the figure. In order to view the DVI version, download both files below. Store them in the same directory, and name the encapsulated PostScript files "`cj9803f5.eps`" and "`cj9803f6.eps`".- DVI (177,252 bytes)
**Encapsulated PostScript**used in Figure 5 (`cj9803f5.eps`, 5,430 bytes)**Encapsulated PostScript**used in Figure 6 (`cj9803f6.eps`, 7,553 bytes)

**PostScript**(681,372 bytes)- PDF (551,705 bytes)
- Audio by
**AsTeR**(to appear)

- Source materials for custom formatting
**LaTeX**(`cj98-03.tex`, 122,676 bytes)**BIBTeX**(`cj98-03.bib`, 12,379 bytes)- Parameter settings for custom
formatting (
`cjropts.tex`, 165 bytes) - Self citation in
**BIBTeX**(292 bytes)

- Online discussion
- Instructions for Readers

DOI: 10.4086/cjtcs.1998.003

Article 2 Article 4

Volume 1998 Published articles

Article 2 Article 4

Volume 1998 Published articles

Last modified: Mon Dec 7 21:14:23 CST 1998