CJTCS Volume 1998 Article 3
Self-Stabilizing Unidirectional Network Algorithms by Power Supply
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 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)
-
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
".
- 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)
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 2
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 4
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 1998
Published articles
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif){kind=logo}
Last modified: Mon Dec 7 21:14:23 CST 1998