Near-optimal knowledge-free resilient leader election

Yuanqiu Mo; Giorgio Audrito; Soura Dasgupta; Jacob Beal

doi:10.1016/j.automatica.2022.110583

Back

Near-optimal knowledge-free resilient leader election

Journal article

Peer reviewed

Near-optimal knowledge-free resilient leader election

Yuanqiu Mo, Giorgio Audrito, Soura Dasgupta and Jacob Beal

Automatica (Oxford), Vol.146, 110583

12/01/2022

DOI: 10.1016/j.automatica.2022.110583

View Online

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.

Engineering

Technology

Automation & Control Systems

Engineering, Electrical & Electronic

Science & Technology

Details

Title: Subtitle: Near-optimal knowledge-free resilient leader election
Creators: Yuanqiu Mo - Southeast University
Giorgio Audrito - Univ Turin, I-10149 Turin, TO, Italy
Soura Dasgupta - Univ Iowa, Iowa City, IA 52242 USA
Jacob Beal - Raytheon BBN Technol, Cambridge, MA 02138 USA
Resource Type: Journal article
Publication Details: Automatica (Oxford), Vol.146, 110583
DOI: 10.1016/j.automatica.2022.110583
ISSN: 0005-1098
eISSN: 1873-2836
Publisher: Elsevier
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

19 Record Views

11 Times Cited - Web of Science