Sinkless Orientation Made Simple

AuthorBalliu, Alkida; Korhonen, Janne H.; Kuhn, Fabian; Lievonen, Henrik; Olivetti, Dennis; Pai, Shreyas; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Studený, Jan; Suomela, Jukka; Uitto, Jara
TypeConference Paper
AbstractThe 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.
ConferenceSymposium on Simplicity in Algorithms 2023