Content-oblivious leader election on rings
Distributed Computing · 2026-06 · 39 (2)
DOI: 10.1007/s00446-025-00491-x ↗Kurz gefasst
Fachartikel in der Zeitschrift Distributed Computing, online erschienen am 02.04.2026. Verfasst von Fabian Frei und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: CISPA - Helmholtz-Zentrum für Informationssicherheit gGmbH.
Abstract (Originalsprache)
In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation. Our goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n \cdot \textsf{ID}_{\max })$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{ID}_{\max }$$\end{document} is the maximal assigned ID. As it turns out, this dependency on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{ID}_{\max }$$\end{document} is inherent: we show a lower bound of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n \log {\textsf{ID}_{\max }})$$\end{document} messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings. Here, however, the algorithm does not terminate but only quiescently stabilizes: all nodes eventually settle on an internal decision and stop receiving messages. Preliminary versions of parts of this research have appeared at the conferences PODC 2024 as a brief announcement and at DISC 2024 as a full paper.
Förderung
- CISPA - Helmholtz-Zentrum für Informationssicherheit gGmbH
Zitieren
APA
Frei, F., Gelles, R., Ghazy, A., & Nolin, A. (2026). Content-oblivious leader election on rings. Distributed Computing, 39(2). https://doi.org/10.1007/s00446-025-00491-x
Vancouver
Frei F, Gelles R, Ghazy A, Nolin A. Content-oblivious leader election on rings. Distributed Computing. 2026;39(2). doi:10.1007/s00446-025-00491-x
BibTeX
@article{Frei2026,
author = {Frei, Fabian and Gelles, Ran and Ghazy, Ahmed and Nolin, Alexandre},
title = {Content-oblivious leader election on rings},
journal = {Distributed Computing},
year = {2026},
volume = {39},
number = {2},
doi = {10.1007/s00446-025-00491-x}
}
EUVIMED