2026-07-23T00:29:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24867 2026-02-09T07:42:10Z ddc:004 open_access

Brief Announcement: Non-Uniform Content-Oblivious Leader Election on Oriented Asynchronous Rings Chalopin, Jérémie Chang, Yi-Jun Chen, Lyuting Di Luna, Giuseppe A. Zhou, Haoran Content-Oblivious Networks Leader Election Oriented Rings Asynchronous Systems In this paper, we study the leader election problem in oriented ring networks under content-oblivious asynchronous message-passing systems, where an adversary may arbitrarily corrupt message contents. Frei et al. (DISC 2024) recently presented a uniform terminating leader election algorithm for oriented rings in this setting, with message complexity O(n ID_{max}) on a ring of size n, where ID_{max} is the largest identifier in the system. In this paper, we investigate the message complexity of leader election in this model, showing that no uniform algorithm can solve the problem if each process is limited to sending a constant number of messages in one direction. Interestingly, this limitation hinges on the uniformity assumption. In the non-uniform setting - where processes know an upper bound U ≥ n on the ring size - we present an algorithm with message complexity O(n U ID_{min}), in which each process sends O(U ID_{min}) messages clockwise and only three messages counter-clockwise. Here, ID_{min} is the smallest identifier in the system. This dependence on the identifiers compares favorably with the dependence on ID_{max} of Frei et al. (DISC 2024). We also show a non-uniform algorithm where each process sends O(U logID_{min}) messages in one direction and O(logID_{min}) in the other. The factor log ID_{min} is optimal, matching the lower bound of Frei et al. (DISC 2024). Finally, in the anonymous setting, we propose a randomized algorithm where each process sends only O(log² U) messages, with a success probability of 1 - U^{-c}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jérémie Chalopin and Yi-Jun Chang and Lyuting Chen and Giuseppe A. Di Luna and Haoran Zhou 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.51 urn:nbn:de:0030-drops-248675 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.51 eng https://creativecommons.org/licenses/by/4.0/legalcode