Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election

The content-oblivious model, introduced by Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022; Distributed Computing 2023), captures an extremely weak form of communication where nodes can only send asynchronous, content-less pulses. They showed that in 2-edge-connected networks, any distributed algorithm can be simulated in the content-oblivious model, provided that a unique leader is designated a priori. Subsequent works of Frei, Gelles, Ghazy, and Nolin (DISC 2024) and Chalopin et al. (DISC 2025) developed content-oblivious leader election algorithms, first for unoriented rings and then for general 2-edge-connected graphs. These results establish that all graph problems are solvable in content-oblivious, 2-edge-connected networks. Much less is known about networks that are not 2-edge-connected. Censor-Hillel, Cohen, Gelles, and Sela 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. Our main contributions are as follows: 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²) 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 𝒢 = {P₃, P₅}, both the 3-path P₃ and the 5-path P₅ admit a quiescently terminating leader election if nodes know the topology exactly. However, if nodes only know that the underlying topology belongs to 𝒢, then terminating leader election is impossible.