Deciding and verifying network properties locally with few output bits
From MaRDI portal
Publication:1988527
DOI10.1007/s00446-019-00355-1zbMath1434.68343OpenAlexW2951207499MaRDI QIDQ1988527
Heger Arfaoui, Andrzej Pelc, Fabien Mathieu, Pierre Fraigniaud, David Ilcinkas
Publication date: 23 April 2020
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-019-00355-1
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Self-stabilizing extensions for message-passing systems
- The local detection paradigm and its applications to self-stabilization
- Node labels in local decision
- What can be verified locally?
- Memory requirements for silent stabilization
- On the recognition of families of graphs with local computations
- Randomized distributed decision
- On distributed Merlin-Arthur decision protocols
- Allowing each node to communicate only once in a distributed system: shared whiteboard models
- Proof labeling schemes
- Locally checkable proofs
- Distributedly Testing Cycle-Freeness
- Subdivided graphs have linear ramsey numbers
- Distributed Computing: A Locality-Sensitive Approach
- What Can be Computed Locally?
- Communication Complexity
- What can be decided locally without identifiers?
- Interactive Distributed Proofs
- Distributed Algorithms Made Secure: A Graph Theoretic Approach
- Towards a complexity theory for local distributed computing
- Distributed verification and hardness of distributed approximation
- On the Impact of Identifiers on Local Decision
- Asymmetric graphs
- On Ordered Groups
This page was built for publication: Deciding and verifying network properties locally with few output bits
