Towards a complexity theory for local distributed computing

DOI10.1145/2499228zbMath1281.68133OpenAlexW1999120866MaRDI QIDQ5395731

Amos Korman, Pierre Fraigniaud, 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

randomized algorithmsnondeterminismoraclelocal decisionlocal distributed algorithms

Mathematics Subject Classification ID

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

Related Items (31)

The ANTS problem ⋮ What can be verified locally? ⋮ Proof-labeling schemes: broadcast, unicast and in between ⋮ Distributed Testing of Distance-k Colorings ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ What can be sampled locally? ⋮ About informatics, distributed computing, and our job: a personal view ⋮ Unnamed Item ⋮ A hierarchy of local decision ⋮ Deciding and verifying network properties locally with few output bits ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ On mobile agent verifiable problems ⋮ Randomized proof-labeling schemes ⋮ What Can be Computed in a Distributed System? ⋮ Randomized distributed decision ⋮ Transmitting once to elect a leader on wireless networks ⋮ A meta-theorem for distributed certification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ Approximate proof-labeling schemes ⋮ Compact distributed certification of planar graphs ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring ⋮ Unnamed Item ⋮ A meta-theorem for distributed certification ⋮ Local certification of graphs with bounded genus ⋮ Introduction to local certification ⋮ Allowing each node to communicate only once in a distributed system: shared whiteboard models

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