Election vs. Selection: Two Ways of Finding the Largest Node in a Graph

Finding the node with the largest label in a network, modeled as an undirected connected graph, is one of the fundamental problems in distributed computing. This is the way in which $\mathit{\text{leader}}\mathit{\text{election}}$ is usually solved. We consider two distinct tasks in which the largest-labeled node is found deterministically. In $\mathit{\text{selection}}$, this node must output 1 and all other nodes must output 0. In $\mathit{\text{election}}$, the other nodes must additionally learn the largest label. Our aim is to compare the difficulty of these two 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 $\mathit{\text{algorithms}}\mathit{\text{with}}\mathit{\text{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 $\mathit{\text{size}}\mathit{\text{of}}\mathit{\text{advice}}$. Consider the class of $n$-node graphs with any diameter $diam\le D$. If time is larger than $diam$, then both tasks can be solved without advice. For the task of $\mathit{\text{election}}$, we show that if time is smaller than $diam$, then the optimal size of advice is $\Theta(\log n)$,andiftimeisexactly$diam$,thentheoptimalsizeofadviceis$\Theta(\log D)$\mathrm{.}Forthetaskof$$\mathit{\text{selection}}$$, the situation changes dramatically, even within the class of rings. Indeed, for the class of rings, we show that, if time is $O(dia{m}^{ϵ})$, for any $ϵ<1$, then the optimal size of advice is $\mathrm{\Theta }(\log D)$, and, if time is $\mathrm{\Theta }(diam)$ (and at most $diam$) then this optimal size is $\mathrm{\Theta }(\log \log D)$.