---
abstract: 'We consider the problem of electing a leader among nodes in a highly dynamic network where the adversary has unbounded capacity to insert and remove nodes (including the leader) from the network and change connectivity at will. We present a randomized algorithm that (re)elects a leader in $O(D\log n)$ rounds with high probability, where $D$ is a bound on the dynamic diameter of the network and $n$ is the maximum number of nodes in the network at any point in time. We assume a model of broadcast-based communication where a node can send only $1$ message of $O(\log n)$ bits per round and is not aware of the receivers in advance. Thus, our results also apply to mobile wireless ad-hoc networks, improving over the optimal (for deterministic algorithms) $O(Dn)$ solution presented at FOMC 2011. We show that our algorithm is optimal by proving that [*any*]{} randomized Las Vegas algorithm takes at least $\Omega(D\log n)$ rounds to elect a leader with high probability, which shows that our algorithm yields the best possible (up to constants) termination time.'
author:
- 'John Augustine[^1]'
- 'Tejas Kulkarni$^\ast$'
- 'Paresh Nakhe$^\ast$'
- 'Peter Robinson[^2]'
bibliography:
- 'papers.bib'
- 'papers1.bib'
- 'papers2.bib'
- 'leader.bib'
title: 'Robust Leader Election in a Fast-Changing World'
---

[^1]: Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, India. : [augustine@cse.iitm.ac.in, tejasvijaykulkarni@gmail.com, paresh.nakhe@gmail.com]{}.

[^2]: Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371. : [peter.robinson@ntu.edu.sg]{}
