Near-optimal knowledge-free resilient leader election (Q2097737)

Leader election is a fundamental problem in distributed systems, in which a network of nodes collectively select a single leader in a distributed and resilient fashion. Resilience ensures election of a single leader and recovery from transient perturbations such as the disappearance of leaders, temporary emergence of false leaders, and link failures that do not disconnect the graph. This problem 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. Leader election studies have considered time, space, and message complexity of deterministic leader election in general networks with identifiers, in probabilistic election in anonymous networks, and in networks like ring, complete, and asynchronous graphs. 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, the problem is considered in the context of open, complex distributed systems such as smart cities and the Internet of Things, which can have large numbers of devices and intermittent perturbation of both network membership and topology. A resilient leader election algorithm is presented with O(diameter) stabilization time, small messages, and no prior knowledge of the network. In this paper, all the authors assume is that each node carries a unique identifier, a requirement common to many networking algorithms, and exchanges messages with its neighbors in synchronous rounds. The algorithm is based on aggregate computing approach that offers a layered abstraction to simplifying the design, creation and maintenance of complex open distributed systems. The approach is based on composition of resilient algorithmic ``building blocks''. The algorithm uses a feedback interconnection of G-blocks that spread information through a network of devices and C-blocks that summarize salient information about the network to be used by interacting units. The authors show that the algorithm is globally uniformly and asymptotically stable and resilient to transient perturbations. A key design function \(g(\cdot)\) determines the dependence of the radius of influence on the the pseudo-diameter estimate. It defines important performance attributes: a fast-growing \(g(\cdot)\) will delay discarding of obsolete data, while a slow-growing \(g(\cdot)\) will slow down convergence to a single leader. It is proven that the trade-off is optimized for the best asymptotic behavior with \(g(x)= (1+\sqrt{2})x\), guaranteeing a near-optimal time complexity of \((2 + 2\sqrt{2})\cdot diameter + o(diameter)\) rounds for stabilization. Simulations are given with asynchronous rounds, singular and persistent perturbations. The authors show that their algorithm compares favorably to the most directly comparable prior one, improving the transient behavior and being able to better withstand persistent perturbations.