English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Finding the node with the largest label in a network, modeled as anundirected connected graph, is one of the fundamental problems in distributedcomputing. This is the way in which $\textit{leader election}$ is usuallysolved. We consider two distinct tasks in which the largest-labeled node isfound deterministically. In $\textit{selection}$, this node must output 1 andall other nodes must output 0. In $\textit{election}$, the other nodes mustadditionally learn the largest label. Our aim is to compare the difficulty ofthese two tasks executed under stringent running time constraints. The measureof difficulty is the amount of information that nodes of the network mustinitially possess in order to solve the given task in an imposed amount oftime. Following the standard framework of $\textit{algorithms with advice}$,this information (a single binary string) is provided to all nodes at the startby an oracle knowing the entire graph. The length of this string is called the$\textit{size of advice}$. Consider the class of $n$-node graphs with anydiameter $diam \leq D$. If time is larger than $diam$, then both tasks can besolved without advice. For the task of $\textit{election}$, we show that iftime is smaller than $diam$, then the optimal size of advice is $\Theta(\logn)$, and if time is exactly $diam$, then the optimal size of advice is$\Theta(\log D)$. For the task of $\textit{selection}$, the situation changesdramatically, even within the class of rings. Indeed, for the class of rings,we show that, if time is $O(diam^{\epsilon})$, for any $\epsilon <1$, then theoptimal size of advice is $\Theta(\log D)$, and, if time is $\Theta(diam)$ (andat most $diam$) then this optimal size is $\Theta(\log \log D)$.

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