Brief Announcement: Classification of Distributed Binary Labeling Problems

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

104 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
OtsikkoPODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
KustantajaACM
Sivut349-351
Sivumäärä3
ISBN (elektroninen)9781450375825
DOI - pysyväislinkit
TilaJulkaistu - 31 heinäk. 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaACM Symposium on Principles of Distributed Computing - Virtual, Online, Italia
Kesto: 3 elok. 20207 elok. 2020
Konferenssinumero: 39

Conference

ConferenceACM Symposium on Principles of Distributed Computing
LyhennettäPODC
Maa/AlueItalia
KaupunkiVirtual, Online
Ajanjakso03/08/202007/08/2020

Sormenjälki

Sukella tutkimusaiheisiin 'Brief Announcement: Classification of Distributed Binary Labeling Problems'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä