Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.23297 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909932082692096 |
|---|---|
| author | Chang, Yi-Jun Chen, Lyuting Zhou, Haoran |
| author_facet | Chang, Yi-Jun Chen, Lyuting Zhou, Haoran |
| contents | The content-oblivious model, introduced by Censor-Hillel, Cohen, Gelles, and Sel (PODC 2022; Distributed Computing 2023), captures an extremely weak form of communication where nodes can only send asynchronous, content-less pulses. Censor-Hillel, Cohen, Gelles, and Sel showed that no non-constant function $f(x,y)$ can be computed correctly by two parties using content-oblivious communication over a single edge, where one party holds $x$ and the other holds $y$. This seemingly ruled out many natural graph problems on non-2-edge-connected graphs.
In this work, we show that, with the knowledge of network topology $G$, leader election is possible in a wide range of graphs.
Impossibility: Graphs symmetric about an edge admit no randomized terminating leader election algorithm, even when nodes have unique identifiers and full knowledge of $G$.
Leader election algorithms: Trees that are not symmetric about any edge admit a quiescently terminating leader election algorithm with topology knowledge, even in anonymous networks, using $O(n^2)$ messages, where $n$ is the number of nodes. Moreover, even-diameter trees admit a terminating leader election given only the knowledge of the network diameter $D = 2r$, with message complexity $O(nr)$.
Necessity of topology knowledge: In the family of graphs $\mathcal{G} = \{P_3, P_5\}$, both the 3-path $P_3$ and the 5-path $P_5$ admit a quiescently terminating leader election if nodes know the topology exactly. However, if nodes only know that the underlying topology belongs to $\mathcal{G}$, then terminating leader election is impossible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_23297 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election Chang, Yi-Jun Chen, Lyuting Zhou, Haoran Distributed, Parallel, and Cluster Computing The content-oblivious model, introduced by Censor-Hillel, Cohen, Gelles, and Sel (PODC 2022; Distributed Computing 2023), captures an extremely weak form of communication where nodes can only send asynchronous, content-less pulses. Censor-Hillel, Cohen, Gelles, and Sel showed that no non-constant function $f(x,y)$ can be computed correctly by two parties using content-oblivious communication over a single edge, where one party holds $x$ and the other holds $y$. This seemingly ruled out many natural graph problems on non-2-edge-connected graphs. In this work, we show that, with the knowledge of network topology $G$, leader election is possible in a wide range of graphs. Impossibility: Graphs symmetric about an edge admit no randomized terminating leader election algorithm, even when nodes have unique identifiers and full knowledge of $G$. Leader election algorithms: Trees that are not symmetric about any edge admit a quiescently terminating leader election algorithm with topology knowledge, even in anonymous networks, using $O(n^2)$ messages, where $n$ is the number of nodes. Moreover, even-diameter trees admit a terminating leader election given only the knowledge of the network diameter $D = 2r$, with message complexity $O(nr)$. Necessity of topology knowledge: In the family of graphs $\mathcal{G} = \{P_3, P_5\}$, both the 3-path $P_3$ and the 5-path $P_5$ admit a quiescently terminating leader election if nodes know the topology exactly. However, if nodes only know that the underlying topology belongs to $\mathcal{G}$, then terminating leader election is impossible. |
| title | Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2511.23297 |