Classification of Distributed Binary Labeling Problems

dc.contributorAalto Universityen
dc.contributor.authorBalliu, Alkidaen_US
dc.contributor.authorSebastian, Brandten_US
dc.contributor.authorEfron, Yuvalen_US
dc.contributor.authorHirvonen, Juhoen_US
dc.contributor.authorMaus, Yannicen_US
dc.contributor.authorOlivetti, Dennisen_US
dc.contributor.authorSuomela, Jukkaen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorAttiya, Hagiten_US
dc.contributor.groupauthorProfessorship Suomela J.en
dc.contributor.groupauthorComputer Science - Algorithms and Theoretical Computer Science (TCS)en
dc.contributor.organizationSwiss Federal Institute of Technology Zurichen_US
dc.contributor.organizationTechnion - Israel Institute of Technologyen_US
dc.contributor.organizationAlbert-Ludwigs-Universität Freiburgen_US
dc.description| openaire: EC/H2020/755839/EU//BANDWIDTH
dc.description.abstractWe present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. 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, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity Θ(log^* n), and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). 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. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.en
dc.description.versionPeer revieweden
dc.identifier.citationBalliu, A, Sebastian, B, Efron, Y, Hirvonen, J, Maus, Y, Olivetti, D & Suomela, J 2020, Classification of Distributed Binary Labeling Problems . in H Attiya (ed.), 34th International Symposium on Distributed Computing (DISC 2020) . Leibniz International Proceedings in Informatics (LIPIcs), vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Virtual, Online, Germany, 12/10/2020 .
dc.identifier.otherPURE UUID: 81e6e001-1632-4c67-8d7a-5bcfddd06ee2en_US
dc.identifier.otherPURE ITEMURL:
dc.identifier.otherPURE FILEURL:
dc.publisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
dc.relation.ispartofInternational Symposium on Distributed Computingen
dc.relation.ispartofseries34th International Symposium on Distributed Computing (DISC 2020)en
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics (LIPIcs)en
dc.relation.ispartofseriesVolume 179en
dc.titleClassification of Distributed Binary Labeling Problemsen
dc.typeConference article in proceedingsfi