Alkida Balliu · Janne H. Korhonen · Fabian Kuhn · Henrik Lievonen · Dennis Olivetti · Shreyas Pai · Ami Paz · Joel Rybicki · Stefan Schmid · Jan Studený · Jukka Suomela · Jara Uitto

Sinkless orientation made simple

SOSA 2023 · SIAM Symposium on Simplicity in Algorithms, Florence, Italy, January 2023 · doi:10.1137/1.9781611977585.ch17

authors’ version publisher’s version arXiv.org

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

Links

Brief Version

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.