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 proceedingConference contributionScientificpeer-review

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 languageEnglish
Title of host publicationPODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
PublisherACM
Pages349-351
Number of pages3
ISBN (Electronic)9781450375825
DOIs
Publication statusPublished - 31 Jul 2020
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Principles of Distributed Computing - Virtual, Online, Italy
Duration: 3 Aug 20207 Aug 2020
Conference number: 39

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
CountryItaly
CityVirtual, Online
Period03/08/202007/08/2020

Keywords

  • distributed computational complexity
  • graph problems
  • LOCAL model
  • locally checkable labeling problems

Fingerprint

Dive into the research topics of 'Brief Announcement: Classification of Distributed Binary Labeling Problems'. Together they form a unique fingerprint.

Cite this