Sinkless Orientation Made Simple
Balliu A, Korhonen J, Kuhn F, Lievonen H, Olivetti D, Pai S, Paz A, Rybicki J, Schmid S, Studený J, Suomela J, Uitto J. 2023.Sinkless Orientation Made Simple. In: Symposium on Simplicity in Algorithms. , 175–191.
Download (ext.)
Book Chapter
| Published
| English
Author
Balliu, Alkida;
Korhonen, JanneISTA;
Kuhn, Fabian;
Lievonen, Henrik;
Olivetti, Dennis;
Pai, Shreyas;
Paz, Ami;
Rybicki, JoelISTA 
;
Schmid, Stefan;
Studený, Jan;
Suomela, Jukka;
Uitto, Jara
All
;
Schmid, Stefan;
Studený, Jan;
Suomela, Jukka;
Uitto, Jara
All
Department
Grant
Abstract
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is Ω(log n) in the deterministic LOCAL model and O(log log n) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.
Publishing Year
Date Published
2023-01-12
Book Title
Symposium on Simplicity in Algorithms
Publisher
2023 Society for Industrial and Applied Mathematics
Acknowledgement
We thank the anonymous reviewers for their helpful feedback on previous versions of this work. Parts ofthis work appeared in DISC 2021 as a brief announcement [ 21]. This work was supported in part by theEuropean Research Council (ERC) under the European Union’s Horizon 2020 research and innovationprogramme (grant agreement No 805223 ScaleML), the Academy of Finland (grant agreement No 333837),the Austrian Science Fund (FWF) and netIDEE (grant agreement No P 33775-N), and the AustrianScience Fund (FWF) project DELTA (grant agreement No I 5025-N).
Page
175-191
Conference
SOSA: Symposium on Simplicity in Algorithms
Conference Location
Florence, Italy
Conference Date
2023-01-23 – 2023-01-25
IST-REx-ID
Cite this
Balliu A, Korhonen J, Kuhn F, et al. Sinkless Orientation Made Simple. In: Symposium on Simplicity in Algorithms. 2023 Society for Industrial and Applied Mathematics; 2023:175-191. doi:10.1137/1.9781611977585.ch17
Balliu, A., Korhonen, J., Kuhn, F., Lievonen, H., Olivetti, D., Pai, S., … Uitto, J. (2023). Sinkless Orientation Made Simple. In Symposium on Simplicity in Algorithms (pp. 175–191). Florence, Italy: 2023 Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977585.ch17
Balliu, Alkida, Janne Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, et al. “Sinkless Orientation Made Simple.” In Symposium on Simplicity in Algorithms, 175–91. 2023 Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/1.9781611977585.ch17.
A. Balliu et al., “Sinkless Orientation Made Simple,” in Symposium on Simplicity in Algorithms, 2023 Society for Industrial and Applied Mathematics, 2023, pp. 175–191.
Balliu A, Korhonen J, Kuhn F, Lievonen H, Olivetti D, Pai S, Paz A, Rybicki J, Schmid S, Studený J, Suomela J, Uitto J. 2023.Sinkless Orientation Made Simple. In: Symposium on Simplicity in Algorithms. , 175–191.
Balliu, Alkida, et al. “Sinkless Orientation Made Simple.” Symposium on Simplicity in Algorithms, 2023 Society for Industrial and Applied Mathematics, 2023, pp. 175–91, doi:10.1137/1.9781611977585.ch17.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2108.02655
Google Scholar