Finding the node with the largest label in a labeled network, modeled as an undirected connected graph, is one of the fundamental problems in distributed computing. This is the way in which  leader election  is usually solved. We consider two distinct tasks in which the largest-labeled node is found deterministically. In  selection , this node has to output 1 and all other nodes have to output 0. In  election , the other nodes must additionally learn the largest label (everybody has to know who is the elected leader). Our aim is to compare the difficulty of these two seemingly similar tasks executed under stringent running time constraints. The measure of difficulty is the amount of information that nodes of the network must initially possess, in order to solve the given task in an imposed amount of time. Following the standard 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 graph. The length of this string is called the  size of advice . The paradigm of algorithms with advice has a far-reaching importance in the realm of network algorithms. Lower bounds on the size of advice give us impossibility results based strictly on the  amount  of initial knowledge outlined in a model's description. This more general approach should be contrasted with traditional results that focus on specific  kinds  of information available to nodes, such as the size, diameter, or maximum node degree. Consider the class of n-node graphs with any diameter diam ≤ D, for some integer D. If time is larger than diam, then both tasks can be solved without advice. For the task of  election , we show that if time is smaller than $diam$, then the optimal size of advice is Θ(log n), and if time is exactly diam, then the optimal size of advice is Θ(log D). For the task of  selection , the situation changes dramatically, even within the class of rings. Indeed, for the class of rings, we show that, if time is O(diam e ), for any e  exponential  increase of difficulty (measured by the size of advice) between selection in time O(diam e ), for any e
['Avery Miller', 'Andrzej Pelc']
Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?