Leader Election in Sparse Dynamic Networks with Churn

Abstract

We investigate the problem of electing a leader in a sparse but well-connected synchronous dynamic network in which up to a fraction of the nodes chosen adversarially can leave/join the network per time step. At this churn rate, all nodes in the network can be replaced by new nodes in a constant number of rounds. Moreover, the adversary can shield a fraction of the nodes (which may include the leader) by repeatedly churning their neighborhood and, thus, hindering, their communication with the rest of the network. However, empirical studies in peer-to-peer networks have shown that a significant fraction of the nodes are usually stable and well connected. It is, therefore, natural to take advantage of such stability to establish a leader that can maintain good communication with the rest of the nodes. Because the dynamics could change eventually, it is also essential to reelect a new leader whenever the current leader either has left the network or is not well-connected with rest of the nodes. In such reelections, care must be taken to avoid premature and spurious leader election resulting in more than one leader being present in the network at the same time. We assume a broadcast-based communication model in which each node can send up to O(log³n) bits per round and is unaware of its receivers a priori. We present a randomized algorithm that can, in O(log n) rounds, detect and reach consensus about the health of the leader (i.e., whether it is able to maintain good communication with rest of the network). In the event that the network decides that the leader’s ability to communicate is unhealthy, a new leader is reelected in a further O(log²n) rounds. Our running times hold with high probability provided a sufficiently large fraction of the nodes remain stable during the reelection process. Furthermore, we are guaranteed with high probability that there is at most one leader at any time.

Notes

¹We crucially include the notion of maintenance along with leader election because in highly dynamic networks, in addition to the traditional notion of leader election, there is also a need to maintain the leader. In particular, we might need to check the availability of the leader and, if needed, initiate a new leader election.

²Throughout this article “with high probability” (abbreviated to w.h.p) refers to probability for any fixed c ≥ 1, and n is the number of nodes in the network at any time, which we assume to be stable.

³In explaining algorithms via pseudocode in this article, we will only state the initial flooding with the appropriate conditioning that controls the extent to which the message is flooded. The repeated flooding (based on the condition) will not be explicitly stated, but rather implicitly assumed.