SOSA 2023 · SIAM Symposium on Simplicity in Algorithms, Florence, Italy, January 2023 · doi:10.1137/1.9781611977585.ch17
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 $\Omega(\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.
Telikepalli Kavitha and Kurt Mehlhorn (Eds.): Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA), pages 175–191, SIAM, 2023