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.
Original languageEnglish
Title of host publication2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023
PublisherSociety for Industrial and Applied Mathematics
ISBN (Electronic)978-1-61197-758-5
DOIs
Publication statusPublished - 12 Jan 2023
MoE publication typeA4 Conference publication
EventSymposium on Simplicity in Algorithms - Grand Hotel Mediterraneo, Florence, Italy
Duration: 23 Jan 202325 Jan 2023
https://www.siam.org/conferences/cm/conference/sosa23

Conference

ConferenceSymposium on Simplicity in Algorithms
Abbreviated titleSOSA
Country/TerritoryItaly
CityFlorence
Period23/01/202325/01/2023
Internet address

Fingerprint

Dive into the research topics of 'Sinkless Orientation Made Simple'. Together they form a unique fingerprint.

Cite this