Self-Stabilizing Weak Leader Election in Anonymous Trees Using Constant Memory per Edge
Document Type
Article
Publication Date
1-1-2017
Publication Title
Parallel Processing Letters
Volume
27
Issue
2
Abstract
We propose a deterministic silent self-stabilizing algorithm for the weak leader election problem in anonymous trees. Our algorithm is designed in the message passing model, and requires only O(1) bits of memory per edge. It does not necessitate the a priori knowledge of any global parameter on the network. Finally, its stabilization time is at most 3D2×(X+2Imax+2) time units, where is the diameter of the network, X is an upper bound on the time to execute some recurrent code by processes, and Imax is the maximal number of messages initially in a link. © 2017 World Scientific Publishing Company.
Keywords
Self-stabilization; Weak leader election; Anonymous tree; Message passing; Intermittent faults
Language
english
Repository Citation
Datta, A. K.,
Devismes, S.,
Larmore, L. L.,
Villain, V.
(2017).
Self-Stabilizing Weak Leader Election in Anonymous Trees Using Constant Memory per Edge.
Parallel Processing Letters, 27(2),
http://dx.doi.org/10.1142/S0129626417500025