Time vs. Information Tradeoffs for Leader Election in Anonymous Trees

Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this article, we study deterministic leader election in anonymous trees.

Our aim is to establish tradeoffs between the allocated time τ and the amount of information that has to be given a priori to the nodes to enable leader election in time τ in all trees for which leader election in this time is at all possible. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the size of advice. For a given time τ allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time τ.

For most values of τ, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let T be an n-node tree of diameter diam ⩽ D. While leader election in time diam can be performed without any advice, for time diam − 1 we give tight upper and lower bounds of Θ(log D). For time diam − 2 we give tight upper and lower bounds of Θ(log D) for even values of diam, and tight upper and lower bounds of Θ(log n) for odd values of diam. Moving to shorter time, in the interval [β · diam, diam − 3] for constant β > 1/2, we prove an upper bound of O(nlog n/D) and a lower bound of Ω(n/D), the latter being valid whenever diam is odd or when the time is at most diam − 4. Hence, with the exception of the special case when diam is even and time is exactly diam − 3, our bounds leave only a logarithmic gap in this time interval. Finally, for time α · diam for any constant α < 1/2 (except for the case of very small diameters), we again give tight upper and lower bounds, this time Θ(n).