Content-Oblivious Leader Election on Rings
<|reference_start|>Content-Oblivious Leader Election on Rings: 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 O(n*ID_max), where ID_max is the maximal assigned ID. As it turns out, this dependency on $ID_max$ is inherent: we show a lower bound of Omega(n*log(ID_max/n)) messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings, where nodes cannot tell which channel leads to which neighbor. In this case, however, the algorithm does not terminate but only reaches quiescence.<|reference_end|>
@article{frei2024content-oblivious,
    title={Content-Oblivious Leader Election on Rings},
    author={Fabian Frei and Ran Gelles and Ahmed Ghazy and Alexandre Nolin},
    journal={arXiv preprint arXiv:2405.03646},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.03646},
    primaryClass={cs.DS cs.DC}
}