Deterministic Distributed Algorithms and Measurable Combinatorics on $Δ$-Regular Forests
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908691619381248 |
|---|---|
| author | Brandt, Sebastian Chang, Yi-Jun Grebík, Jan Grunau, Christoph Rozhoň, Václav Vidnyánszky, Zoltán |
| author_facet | Brandt, Sebastian Chang, Yi-Jun Grebík, Jan Grunau, Christoph Rozhoň, Václav Vidnyánszky, Zoltán |
| contents | We investigate the connections between the fields of distributed computing and measurable combinatorics by considering complexity classes of locally checkable labeling problems on regular forests. We show that the most important deterministic complexity classes from the LOCAL model of distributed computing exactly coincide with well-studied classes in measurable combinatorics. Namely, first we show that a locally checkable labeling problem admits a continuous solution if and only if it can be solved by a deterministic local algorithm with complexity $O(\log^* n)$. Second, our main result states that, surprisingly, a locally checkable labeling problem admits a Baire measurable solution if and only if it can be solved by a local algorithm with complexity $O(\log n)$. These theorems suggest the existence of deeper connections between the two frameworks. Furthermore, the latter result relies on a complete combinatorial characterization of the classes in question, and as a by-product, it shows that membership in these classes is decidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_09329 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Deterministic Distributed Algorithms and Measurable Combinatorics on $Δ$-Regular Forests Brandt, Sebastian Chang, Yi-Jun Grebík, Jan Grunau, Christoph Rozhoň, Václav Vidnyánszky, Zoltán Logic Distributed, Parallel, and Cluster Computing We investigate the connections between the fields of distributed computing and measurable combinatorics by considering complexity classes of locally checkable labeling problems on regular forests. We show that the most important deterministic complexity classes from the LOCAL model of distributed computing exactly coincide with well-studied classes in measurable combinatorics. Namely, first we show that a locally checkable labeling problem admits a continuous solution if and only if it can be solved by a deterministic local algorithm with complexity $O(\log^* n)$. Second, our main result states that, surprisingly, a locally checkable labeling problem admits a Baire measurable solution if and only if it can be solved by a local algorithm with complexity $O(\log n)$. These theorems suggest the existence of deeper connections between the two frameworks. Furthermore, the latter result relies on a complete combinatorial characterization of the classes in question, and as a by-product, it shows that membership in these classes is decidable. |
| title | Deterministic Distributed Algorithms and Measurable Combinatorics on $Δ$-Regular Forests |
| topic | Logic Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2204.09329 |