How much memory is needed for leader election

We study the minimum memory size with which nodes of a network have to be equipped, in order to solve deterministically the leader election problem. Nodes are unlabeled, but ports at each node have arbitrary fixed labelings which, together with the topology of the network, can create asymmetries to be exploited in leader election. We consider two versions of the leader election problem: strong LE in which exactly one leader has to be elected, if this is possible, while all nodes must terminate in a state “infeasible” when the election of a unique leader fails, and weak LE, which differs from strong LE in that no requirement on the behavior of nodes is imposed, if leader election is impossible. Nodes are modeled as identical automata and we ask what is the minimum amount of memory of such an automaton to enable leader election. We show that logarithmic memory is optimal for both strong and weak leader election in the class of arbitrary connected graphs. By contrast we show that strong LE can be accomplished in the class of trees of maximum degree Δ using only O(log log Δ) bits of memory, thus proving an exponential gap in memory requirements for leader election between the class of trees and the class of arbitrary graphs.