Hardness of Minimal Symmetry Breaking in Distributed Computing

Alkida Balliu, Juho Hirvonen, Dennis Olivetti, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

A graph is weakly 2-colored if the nodes are labeled with colors black and white such that each black node is adjacent to at least one white node and vice versa. In this work we study the distributed computational complexity of weak 2-coloring in the standard łocal model of distributed computing, and how it is related to the distributed computational complexity of other graph problems.

First, we show that weak 2-coloring is a minimal distributed symmetry-breaking problem for regular even-degree trees and high-girth graphs: if there is any non-trivial locally checkable labeling problem that is solvable in o(log⋅ n) rounds with a distributed graph algorithm in the middle of a regular even-degree tree, then weak 2-coloring is also solvable in o(log⋅ n) rounds there.

Second, we prove a tight lower bound of Ω(log ⋅ n) for the distributed computational complexity of weak 2-coloring in regular trees; previously only a lower bound of Ω n(log log⋅ n) was known. By minimality, the same lower bound holds for any non-trivial locally checkable problem inside regular even-degree trees.
Original languageEnglish
Title of host publicationProceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019)
PublisherACM
Pages369-378
ISBN (Electronic)978-1-4503-6217-7
DOIs
Publication statusPublished - 2019
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Principles of Distributed Computing - Toronto, Canada
Duration: 29 Jul 20192 Aug 2019
Conference number: 38

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
Country/TerritoryCanada
CityToronto
Period29/07/201902/08/2019

Fingerprint

Dive into the research topics of 'Hardness of Minimal Symmetry Breaking in Distributed Computing'. Together they form a unique fingerprint.

Cite this