Brief Announcement: Toward Uniform Content-Oblivious Leader Election on General Graphs

Summary

In the content-oblivious model, communication is limited to sending content-less pulses over asynchronous channels. Despite this extreme restriction, Censor-Hillel et al. (Dist. Comp., 2023) showed that any computation can be simulated on 2-edge-connected graphs, assuming a designated leader. Subsequent work investigated the necessity of this assumption. Frei et al. (DISC 2024, Dist. Comp. 2026) and Chalopin et al. (DISC 2025) designed content-oblivious leader-election algorithms for rings, thereby eliminating the need for an initial leader. Non-uniform leader election is possible on 2-edge-connected graphs (Chalopin et al., DISC 2025). We extend uniform leader election beyond rings to a significantly broader class of topologies. Specifically, we present a uniform content-oblivious leader-election algorithm for Eulerian graphs with message complexity O(|E| * ID_max), where |E| is the number of edges, and ID_max is the largest identifier in the network. While the feasibility of uniform content-oblivious leader election in arbitrary 2-edge-connected graphs remains open, our result substantially narrows the gap between rings and general 2-edge-connected graphs.