Self-stabilizing leader election in optimal space under an arbitrary scheduler

A silent self-stabilizing asynchronous distributed algorithm, SSLE, is given for the leader election problem in a connected unoriented (bidirectional) network with unique IDs. SSLE also constructs a BFS tree on the network rooted at that leader. SSLE uses O(logn) space per process and stabilizes in...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2011-09, Vol.412 (40), p.5541-5561
Main Authors: Datta, Ajoy K., Larmore, Lawrence L., Vemula, Priyanka
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Bidirectional
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Construction
Distributed algorithm
Elections
Exact sciences and technology
Graph theory
Leader election
Mathematics
Miscellaneous
Networks
Optimization
Sciences and techniques of general use
Self-stabilization
Silent algorithm
Theoretical computing
Trees
Unfair daemon
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A silent self-stabilizing asynchronous distributed algorithm, SSLE, is given for the leader election problem in a connected unoriented (bidirectional) network with unique IDs. SSLE also constructs a BFS tree on the network rooted at that leader. SSLE uses O(logn) space per process and stabilizes in O(n) rounds, against the unfair daemon, where n is the number of processes in the network.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2010.05.001