Towards a complexity theory for local distributed computing

DOI10.1145/2499228MaRDI QIDQ5395731zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, Amos Korman, David Peleg

Publication date 17 February 2014

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2499228

zbMATH Keywords

local decisionlocal distributed algorithmsnondeterminismoraclerandomized algorithms

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• What Can be Computed Locally?
• On the complexity of local distributed graph problems
• On the locality of some NP-complete problems

Cited in

(49)

• What can be verified locally?
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• On mobile agent verifiable problems
• Deciding and verifying network properties locally with few output bits
• Randomized proof-labeling schemes
• Redundancy in distributed proofs
• Compact distributed certification of planar graphs
• A meta-theorem for distributed certification
• Local certification of graphs with bounded genus
• What can be sampled locally?
• A hierarchy of local decision
• A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring
• Allowing each node to communicate only once in a distributed system: shared whiteboard models
• The ANTS problem
• Proof-labeling schemes: broadcast, unicast and in between
• Survey of local algorithms
• The Local Information Dynamics of Distributed Computation in Complex Systems
• Local computation: lower and upper bounds
• The Time-Complexity of Local Decision in Distributed Agreement
• Local Computation Schemes with Partially Ordered Preferences
• What can be verified locally?
• A time hierarchy theorem for the LOCAL model
• scientific article; zbMATH DE number 2156277 (Why is no real title available?)
• Survey of distributed decision
• Infinite networks, halting and local algorithms
• Introduction to local certification
• Redundancy in distributed proofs
• Local verification of global proofs
• Characterizing asynchronous message-passing models through rounds
• Distributed Testing of Distance-k Colorings
• On the Use of Randomness in Local Distributed Graph Algorithms
• scientific article; zbMATH DE number 7407798 (Why is no real title available?)
• What can be computed in a distributed system?
• Approximate proof-labeling schemes
• Making local algorithms wait-free: the case of ring coloring
• scientific article; zbMATH DE number 7765409 (Why is no real title available?)
• Transmitting once to elect a leader on wireless networks
• A meta-theorem for distributed certification
• About informatics, distributed computing, and our job: a personal view
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• The complexity landscape of distributed locally checkable problems on trees
• Locally verifiable distributed SNARGs
• Distributed model checking on graphs of bounded treedepth
• Decreasing verification radius in local certification
• Tight bounds on the message complexity of distributed tree verification
• A LOCAL view of the polynomial hierarchy
• Shared versus private randomness in distributed interactive proofs
• Distributed quantum proofs for replicated data
• An interpretation of Shenoy and Shafer's axioms for local computation

This page was built for publication: Towards a complexity theory for local distributed computing

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