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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

25 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023
Kustantaja	Society for Industrial and Applied Mathematics
ISBN (elektroninen)	978-1-61197-758-5
DOI - pysyväislinkit	https://doi.org/10.1137/1.9781611977585.ch17
Tila	Julkaistu - 12 tammik. 2023
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	Symposium on Simplicity in Algorithms - Grand Hotel Mediterraneo, Florence, Italia Kesto: 23 tammik. 2023 → 25 tammik. 2023 https://www.siam.org/conferences/cm/conference/sosa23

Conference

Conference	Symposium on Simplicity in Algorithms
Lyhennettä	SOSA
Maa/Alue	Italia
Kaupunki	Florence
Ajanjakso	23/01/2023 → 25/01/2023
www-osoite	https://www.siam.org/conferences/cm/conference/sosa23

Pääsy asiakirjaan

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. (Vastuullinen tutkija)
01/09/2020 → 31/08/2024
Projekti: RCF Academy Project

Siteeraa tätä

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. teoksessa 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. julkaisussa 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, Italia, 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

Abstrakti

Conference

Pääsy asiakirjaan

Sormenjälki

Projektit

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

Siteeraa tätä

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