Projects per year
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 | |
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 |
Fingerprint
Dive into the research topics of 'Sinkless Orientation Made Simple'. Together they form a unique fingerprint.Projects
- 1 Finished
-
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