The Distributed Complexity of Locally Checkable Problems on Paths is Decidable

DOI10.1145/3293611.3331606MaRDI QIDQ5145218zbMATH OpenOpenAlexWikidataFDO

Authors Alkida Balliu, Sebastian F. Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela

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/1811.01672

zbMATH Keywords

complexitydecidabilitydistributed computing

Mathematics Subject Classification ID

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

Recommendations

• What Can be Computed Locally?
• Distributed graph problems through an automata-theoretic lens
• The complexity landscape of distributed locally checkable problems on trees
• Brief announcement: Distributed graph problems through an automata-theoretic lens
• Brief Announcement: Classification of Distributed Binary Labeling Problems

Cited in

(10)

• Distributed graph problems through an automata-theoretic Lens
• A new approach on locally checkable problems
• Distributed graph problems through an automata-theoretic lens
• Classification of distributed binary labeling problems
• The complexity landscape of distributed locally checkable problems on trees
• Brief announcement: Distributed graph problems through an automata-theoretic lens
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Completing the node-averaged complexity landscape of LCLs on trees
• Shared randomness helps with local distributed problems
• Shared randomness in locally checkable problems: the role of computational assumptions

This page was built for publication: The Distributed Complexity of Locally Checkable Problems on Paths is Decidable

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