{"ID":2895588,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.08348","arxiv_id":"2507.08348","title":"Content-Oblivious Leader Election in 2-Edge-Connected Networks","abstract":"Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 \u0026 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.","short_abstract":"Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 \u0026 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 comm...","url_abs":"https://arxiv.org/abs/2507.08348","url_pdf":"https://arxiv.org/pdf/2507.08348v3","authors":"[\"Jérémie Chalopin\",\"Yi-Jun Chang\",\"Lyuting Chen\",\"Giuseppe A. Di Luna\",\"Haoran Zhou\"]","published":"2025-07-11T06:48:21Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}