Brief Announcement: Classification of Distributed Binary Labeling Problems

Alkida Balliu; Sebastian Brandt; Yuval Efron; Juho Hirvonen; Yannic Maus; Dennis Olivetti; Jukka Suomela

doi:10.1145/3382734.3405703

Brief Announcement: Classification of Distributed Binary Labeling Problems

Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela

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

126 Downloads (Pure)

Abstract

We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.

Original language	English
Title of host publication	PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
Publisher	ACM
Pages	349-351
Number of pages	3
ISBN (Electronic)	9781450375825
DOIs	https://doi.org/10.1145/3382734.3405703
Publication status	Published - 31 Jul 2020
MoE publication type	A4 Conference publication
Event	ACM Symposium on Principles of Distributed Computing - Virtual, Online, Italy Duration: 3 Aug 2020 → 7 Aug 2020 Conference number: 39

Conference

Conference	ACM Symposium on Principles of Distributed Computing
Abbreviated title	PODC
Country/Territory	Italy
City	Virtual, Online
Period	03/08/2020 → 07/08/2020

Keywords

distributed computational complexity
graph problems
LOCAL model
locally checkable labeling problems

Access to Document

10.1145/3382734.3405703

SCI_Suomela_Brief Announcement_Classification of Distributed Binary Labeling ProblemsAccepted author manuscript, 496 KB

Cite this

@inproceedings{0bbe4bb3b6d8437aa6aa48921b034041,

title = "Brief Announcement: Classification of Distributed Binary Labeling Problems",

abstract = "We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.",

keywords = "distributed computational complexity, graph problems, LOCAL model, locally checkable labeling problems",

author = "Alkida Balliu and Sebastian Brandt and Yuval Efron and Juho Hirvonen and Yannic Maus and Dennis Olivetti and Jukka Suomela",

year = "2020",

month = jul,

day = "31",

doi = "10.1145/3382734.3405703",

language = "English",

pages = "349--351",

booktitle = "PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing",

publisher = "ACM",

address = "United States",

note = "ACM Symposium on Principles of Distributed Computing, PODC ; Conference date: 03-08-2020 Through 07-08-2020",

}

Balliu, A, Brandt, S, Efron, Y, Hirvonen, J, Maus, Y, Olivetti, D & Suomela, J 2020, Brief Announcement: Classification of Distributed Binary Labeling Problems. in PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. ACM, pp. 349-351, ACM Symposium on Principles of Distributed Computing, Virtual, Online, Italy, 03/08/2020. https://doi.org/10.1145/3382734.3405703

Brief Announcement: Classification of Distributed Binary Labeling Problems. / Balliu, Alkida; Brandt, Sebastian; Efron, Yuval et al.
PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. ACM, 2020. p. 349-351.

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

TY - GEN

T1 - Brief Announcement: Classification of Distributed Binary Labeling Problems

AU - Balliu, Alkida

AU - Brandt, Sebastian

AU - Efron, Yuval

AU - Hirvonen, Juho

AU - Maus, Yannic

AU - Olivetti, Dennis

AU - Suomela, Jukka

N1 - Conference code: 39

PY - 2020/7/31

Y1 - 2020/7/31

N2 - We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.

AB - We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.

KW - distributed computational complexity

KW - graph problems

KW - LOCAL model

KW - locally checkable labeling problems

UR - http://www.scopus.com/inward/record.url?scp=85090359898&partnerID=8YFLogxK

U2 - 10.1145/3382734.3405703

DO - 10.1145/3382734.3405703

M3 - Conference article in proceedings

AN - SCOPUS:85090359898

SP - 349

EP - 351

BT - PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing

PB - ACM

T2 - ACM Symposium on Principles of Distributed Computing

Y2 - 3 August 2020 through 7 August 2020

ER -

Brief Announcement: Classification of Distributed Binary Labeling Problems

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this