# Sinkless orientation made simple

SOSA 2023 · SIAM Symposium on Simplicity in Algorithms, Florence, Italy, January 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 $\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.

# Publication

Telikepalli Kavitha and Kurt Mehlhorn (Eds.): Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA), pages 175–191, SIAM, 2023

ISBN 978-1-61197-758-5