An Automatic Speedup Theorem for Distributed Problems

DOI10.1145/3293611.3331611OpenAlexW2964145385WikidataQ130857321 ScholiaQ130857321MaRDI QIDQ5145238FDOQ5145238

Authors: Sebastian F. Brandt 

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.09958

Recommendations

• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed algorithms for the Lovász local lemma and graph coloring
• A time hierarchy theorem for the LOCAL model
• A lower bound for the distributed Lovász local lemma

zbMATH Keywords

distributed graph algorithmsweak coloringlocally checkable problems

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (13)

• The complexity landscape of distributed locally checkable problems on trees
• Linial for lists
• Distributed algorithms for fractional coloring
• Classification of distributed binary labeling problems
• Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
• Distributed coloring of hypergraphs
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• The topology of local computing in networks
• Distributed Lower Bounds for Ruling Sets
• Brief announcement: Efficient load-balancing through distributed token dropping
• Local conflict coloring revisited: Linial for lists
• Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
• Efficient distributed algorithms by using the archimedean time assumption

This page was built for publication: An Automatic Speedup Theorem for Distributed Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145238)