Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.08348 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912543276007424 |
|---|---|
| author | Chalopin, Jérémie Chang, Yi-Jun Chen, Lyuting Di Luna, Giuseppe A. Zhou, Haoran |
| author_facet | Chalopin, Jérémie Chang, Yi-Jun Chen, Lyuting Di Luna, Giuseppe A. Zhou, Haoran |
| contents | Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may suffer an extreme form of alteration errors, rendering messages completely corrupted. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task.
In this work, we present two results:
General 2-edge-connected topologies: First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity $O(m \cdot N \cdot \mathsf{ID}_{\min})$, where $m$ is the number of edges, $N$ is a known upper bound on the number of nodes, and $\mathsf{ID}_{\min}$ is the smallest $\mathsf{ID}$. Combined with the above simulation, this result shows that whenever a size bound $N$ is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture.
Unoriented rings: We then show that the knowledge of $N$ can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity $O(n \cdot \mathsf{ID}_{\max})$ that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous leader election in oriented rings by Frei, Gelles, Ghazy, and Nolin (DISC 2024) and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_08348 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Content-Oblivious Leader Election in 2-Edge-Connected Networks Chalopin, Jérémie Chang, Yi-Jun Chen, Lyuting Di Luna, Giuseppe A. Zhou, Haoran Distributed, Parallel, and Cluster Computing Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may suffer an extreme form of alteration errors, rendering messages completely corrupted. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task. In this work, we present two results: General 2-edge-connected topologies: First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity $O(m \cdot N \cdot \mathsf{ID}_{\min})$, where $m$ is the number of edges, $N$ is a known upper bound on the number of nodes, and $\mathsf{ID}_{\min}$ is the smallest $\mathsf{ID}$. Combined with the above simulation, this result shows that whenever a size bound $N$ is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture. Unoriented rings: We then show that the knowledge of $N$ can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity $O(n \cdot \mathsf{ID}_{\max})$ that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous leader election in oriented rings by Frei, Gelles, Ghazy, and Nolin (DISC 2024) and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions. |
| title | Content-Oblivious Leader Election in 2-Edge-Connected Networks |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.08348 |