Journal article
Near-optimal knowledge-free resilient leader election
Automatica (Oxford), Vol.146, 110583
12/01/2022
DOI: 10.1016/j.automatica.2022.110583
Abstract
Leader election, is a fundamental coordination problem in distributed systems. It has been addressed in many ways for different systems. Among these approaches, resilient leader election algorithms are of particular interest due to the ongoing emergence of open, complex distributed systems such as smart cities and the Internet of Things. However, previous algorithms attaining the optimal scaling of O(diameter) stabilization time complexity either assume some prior knowledge of the network or else that very large messages can be sent. In this paper, we present a resilient leader election algorithm with O(diameter) stabilization time, small messages, and no prior knowledge of the network. This algorithm is based on aggregate computing, which provides a layered approach to algorithm development based on composition of resilient algorithmic "building blocks."With our algorithm, a key design function g(center dot) defines important performance attributes: a fast-growing g(center dot) will delay discarding of obsolete data, while a slow-growing g(center dot) will slow down convergence to a single leader. We prove that the root best asymptotic behavior for g(x) is (1 + root 2)x +o(x), guaranteeing a near-optimal time complexity of (2 + 2 2) diameter + o(diameter) rounds for stabilization. (c) 2022 Elsevier Ltd. All rights reserved.
Details
- Title: Subtitle
- Near-optimal knowledge-free resilient leader election
- Creators
- Yuanqiu Mo - Southeast UniversityGiorgio Audrito - Univ Turin, I-10149 Turin, TO, ItalySoura Dasgupta - Univ Iowa, Iowa City, IA 52242 USAJacob Beal - Raytheon BBN Technol, Cambridge, MA 02138 USA
- Resource Type
- Journal article
- Publication Details
- Automatica (Oxford), Vol.146, 110583
- Publisher
- Elsevier
- DOI
- 10.1016/j.automatica.2022.110583
- ISSN
- 0005-1098
- eISSN
- 1873-2836
- Number of pages
- 13
- Grant note
- Defense Advanced Research Projects Agency (DARPA); United States Department of Defense
- Language
- English
- Date published
- 12/01/2022
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984305989902771
Metrics
8 Record Views