An Aggregate Computing Approach to Self-Stabilizing Leader Election

摘要

Leader election is one of the core coordination problems of distributed systems, and has been addressed in many different ways suitable for different classes of systems. It is unclear, however, whether existing methods will be effective for resilient device coordination in open, complex, networked distributed systems like smart cities, tactical networks, personal networks and the Internet of Things (IoT). Aggregate computing provides a layered approach to developing such systems, in which resilience is provided by a layer comprising a set of adaptive algorithms whose compositions have been shown to cover a large class of coordination activities. In this paper, we show how a feedback interconnection of these basis set algorithms can perform distributed leader election resilient to device topology and position changes. We also characterize a key design parameter that defines some important performance attributes: Too large a value impairs resilience to loss of existing leaders, while too small a value leads to multiple leaders. We characterize the smallest value of this parameter for which the only stationary points have single leaders, and demonstrate resilience of this algorithm through simulations.