Distributed Computing Computational Theory and Mathematics

Non-uniform content-oblivious leader election in 2-edge-connected networks

Chalopin, Jérémie, Chang, Yi-Jun, Chen, Lyuting, Di Luna, Giuseppe A., Zhou, Haoran
Springer Nature · 2026-08-24 · DOI 10.1007/s00446-026-00517-y

Abstract

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. Recently, Frei, Gelles, Ghazy, and Nolin (DISC 2024) refuted this conjecture for the special case of oriented ring topology. They designed two asynchronous content-oblivious leader election algorithms with message complexity $$O(n \cdot \mathsf {ID_{\max }})$$ O ( n · ID max ) , where n is the number of nodes and $$\mathsf {ID_{\max }}$$ ID max is the maximum $$\textsf{ID}$$ ID . The first algorithm stabilizes in unoriented rings without termination detection. The second algorithm quiescently terminates in oriented rings, thus enabling the execution of the simulation algorithm after leader election. 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 }})$$ O ( m · N · ID min ) , where m is the number of edges, N is a known upper bound on the number of nodes, and $$\mathsf {ID_{\min }}$$ ID min is the smallest $$\textsf{ID}$$ 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 \textsf{ID}_{\max })$$ O ( n · ID max ) that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous state of the art and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions.

Read at publisher →