An Automatic Speedup Theorem for Distributed Problems

DOI10.1145/3293611.3331611MaRDI QIDQ5145238zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

distributed graph algorithmslocally checkable problemsweak coloring

Mathematics Subject Classification ID

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

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

Cited in

(17)

• Linial for lists
• Distributed algorithms for fractional coloring
• 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
• Distributed (+1)-coloring via ultrafast graph shattering
• Distributed Lower Bounds for Ruling Sets
• Distributed coloring of hypergraphs
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Local conflict coloring revisited: Linial for lists
• Classification of distributed binary labeling problems
• The complexity landscape of distributed locally checkable problems on trees
• Brief announcement: Efficient load-balancing through distributed token dropping
• The topology of local computing in networks
• The topology of local computing in networks
• Distributed symmetry breaking on power graphs via sparsification
• A speedup theorem for asynchronous computation with applications to consensus and approximate agreement
• Tight lower bounds in the supported LOCAL model

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)