Sinkless Orientation Made Simple
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023
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.Description
Keywords
Other note
Citation
Balliu, A, Korhonen, J H, Kühn, 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 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023. Society for Industrial and Applied Mathematics, Symposium on Simplicity in Algorithms, Florence, Italy, 23/01/2023. https://doi.org/10.1137/1.9781611977585.ch17