Brief announcement: Sinkless orientation is hard also in the supported LOCAL model

Korhonen, Janne; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Suomela, Jukka

Brief announcement: Sinkless orientation is hard also in the supported LOCAL model

Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 58.

Download

2021_LIPIcsDISC_Korhonen.pdf 474.24 KB

DOI

10.4230/LIPIcs.DISC.2021.58

Conference Paper | Published | English

Scopus indexed

Author

Korhonen, Janne^ISTA; Paz, Ami; Rybicki, Joel^ISTA ; Schmid, Stefan; Suomela, Jukka

Department

Alistarh Group

Grant

Elastic Coordination for Scalable Machine Learning

Series Title

LIPIcs

Abstract

We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).

Publishing Year

2021

Date Published

2021-10-04

Proceedings Title

35th International Symposium on Distributed Computing

Acknowledgement

Janne H. Korhonen: Project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.

Volume

209

Article Number

Conference

DISC: Distributed Computing

Conference Location

Freiburg, Germany

Conference Date

2021-10-04 – 2021-10-08

ISBN

9-783-9597-7210-5

ISSN

1868-8969

IST-REx-ID

10219

Cite this

Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In: 35th International Symposium on Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.58

Korhonen, J., Paz, A., Rybicki, J., Schmid, S., & Suomela, J. (2021). Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In 35th International Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.58

Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” In 35th International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.58.

J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement: Sinkless orientation is hard also in the supported LOCAL model,” in 35th International Symposium on Distributed Computing, Freiburg, Germany, 2021, vol. 209.

Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” 35th International Symposium on Distributed Computing, vol. 209, 58, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.DISC.2021.58.

All files available under the following license(s):

Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):