This is an interim version of our Electronic Legal Deposit Catalogue-eJournals and eBooks while we continue to recover from a cyber-attack.
A Resilient Leader Election Algorithm Using Aggregate Computing Blocks⁎Supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0049. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. This document does not contain technology or technical data controlled under either U.S. International Traffic in Arms Regulation or U.S. Export Administration Regulations. Approved for public release, distribution unlimited (DARPA DISTAR case 32200, 10/31/19). Mo was also partially supported by the Australian Research Council under grant DP190100887 and DP160104500. Issue 2 (2020)
Record Type:
Journal Article
Title:
A Resilient Leader Election Algorithm Using Aggregate Computing Blocks⁎Supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0049. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. This document does not contain technology or technical data controlled under either U.S. International Traffic in Arms Regulation or U.S. Export Administration Regulations. Approved for public release, distribution unlimited (DARPA DISTAR case 32200, 10/31/19). Mo was also partially supported by the Australian Research Council under grant DP190100887 and DP160104500. Issue 2 (2020)
Main Title:
A Resilient Leader Election Algorithm Using Aggregate Computing Blocks⁎Supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0049. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. This document does not contain technology or technical data controlled under either U.S. International Traffic in Arms Regulation or U.S. Export Administration Regulations. Approved for public release, distribution unlimited (DARPA DISTAR case 32200, 10/31/19). Mo was also partially supported by the Australian Research Council under grant DP190100887 and DP160104500.
Abstract: Leader election, a fundamental coordination problem in distributed systems, has been addressed in many different ways. Among these works, 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 with O(diameter) stabilization time complexity either assume some prior knowledge of the network or 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 parameter K defines important performance attributes: a larger K will delay the recovery from loss of current leader, while a small K may lead to multiple leaders, and the algorithm will stabilize with O(diameter) time complexity when K ≥ 2.