Sinkless Orientation Made Simple

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

doi:10.1137/1.9781611977585.ch17

Sinkless Orientation Made Simple

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

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

52 Downloads (Pure)

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 language	English
Title of host publication	2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023
Publisher	Society for Industrial and Applied Mathematics
ISBN (Electronic)	978-1-61197-758-5
DOIs	https://doi.org/10.1137/1.9781611977585.ch17
Publication status	Published - 12 Jan 2023
MoE publication type	A4 Conference publication
Event	Symposium on Simplicity in Algorithms - Grand Hotel Mediterraneo, Florence, Italy Duration: 23 Jan 2023 → 25 Jan 2023 https://www.siam.org/conferences/cm/conference/sosa23

Conference

Conference	Symposium on Simplicity in Algorithms
Abbreviated title	SOSA
Country/Territory	Italy
City	Florence
Period	23/01/2023 → 25/01/2023
Internet address	https://www.siam.org/conferences/cm/conference/sosa23

Access to Document

10.1137/1.9781611977585.ch17

Sinkless Orientation Made SimpleFinal published version, 888 KB

LocalMend /Suomela: Local Checking, Solving, and MendingNew Perspectives of Distributed Computing (LocalMend)
Suomela, J. (Principal investigator), Lievonen, H. (Project Member), Melnyk, D. (Project Member), Vahidi, H. (Project Member), Studeny, J. (Project Member) & Akbari, A. (Project Member)
01/09/2020 → 31/08/2024
Project: Academy of Finland: Other research funding

Cite this

Balliu, A., Korhonen, J. H., Kühn, F., Lievonen, H., Olivetti, D., Pai, S., Paz, A., Rybicki, J., Schmid, S., Studený, J., Suomela, J., & Uitto, J. (2023). Sinkless Orientation Made Simple. In 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023 Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977585.ch17

@inproceedings{432153e1fe0f46658dae69a1bebbf3bd,

title = "Sinkless Orientation Made Simple",

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.",

author = "Alkida Balliu and Korhonen, {Janne H.} and Fabian K{\"u}hn and Henrik Lievonen and Dennis Olivetti and Shreyas Pai and Ami Paz and Joel Rybicki and Stefan Schmid and Jan Studen{\'y} and Jukka Suomela and Jara Uitto",

year = "2023",

month = jan,

day = "12",

doi = "10.1137/1.9781611977585.ch17",

language = "English",

booktitle = "2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

note = "Symposium on Simplicity in Algorithms, SOSA ; Conference date: 23-01-2023 Through 25-01-2023",

url = "https://www.siam.org/conferences/cm/conference/sosa23",

}

Balliu, A, Korhonen, JH, Kühn, F, Lievonen, H, Olivetti, D, Pai, S, Paz, A, Rybicki, J, Schmid, S, Studený, J , Suomela, J & Uitto, J 2023, Sinkless Orientation Made Simple. in 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023. Society for Industrial and Applied Mathematics, Symposium on Simplicity in Algorithms, Florence, Italy, 23/01/2023. https://doi.org/10.1137/1.9781611977585.ch17

TY - GEN

T1 - Sinkless Orientation Made Simple

AU - Balliu, Alkida

AU - Korhonen, Janne H.

AU - Kühn, Fabian

AU - Lievonen, Henrik

AU - Olivetti, Dennis

AU - Pai, Shreyas

AU - Paz, Ami

AU - Rybicki, Joel

AU - Schmid, Stefan

AU - Studený, Jan

AU - Suomela, Jukka

AU - Uitto, Jara

PY - 2023/1/12

Y1 - 2023/1/12

N2 - 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.

AB - 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.

U2 - 10.1137/1.9781611977585.ch17

DO - 10.1137/1.9781611977585.ch17

M3 - Conference article in proceedings

BT - 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023

PB - Society for Industrial and Applied Mathematics

T2 - Symposium on Simplicity in Algorithms

Y2 - 23 January 2023 through 25 January 2023

ER -

Sinkless Orientation Made Simple

Abstract

Conference

Access to Document

Fingerprint

Projects

LocalMend /Suomela: Local Checking, Solving, and MendingNew Perspectives of Distributed Computing (LocalMend)

Cite this

LocalMend /Suomela: Local Checking, Solving, and MendingNew Perspectives of Distributed Computing (LocalMend)