An Automatic Speedup Theorem for Distributed Problems

DOI10.1145/3293611.3331611OpenAlexW2964145385WikidataQ130857321 ScholiaQ130857321MaRDI QIDQ5145238FDOQ5145238

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 algorithmsweak coloringlocally checkable problems

Mathematics Subject Classification ID

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

Cited In (14)

• Locally checkable problems in rooted trees
• The complexity landscape of distributed locally checkable problems on trees
• Linial for lists
• Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
• Distributed algorithms for fractional coloring
• Classification of distributed binary labeling problems
• 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)