Redundancy in distributed proofs

DOI10.1007/s00446-020-00386-zOpenAlexW3091964988WikidataQ113905016 ScholiaQ113905016MaRDI QIDQ2025853

Mor Perry, Ami Paz, Pierre Fraigniaud, Juho Hirvonen, Laurent Feuilloley

Publication date: 17 May 2021

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.03031

zbMATH Keywords

nondeterminismdistributed verificationdistributed graph algorithmsproof-labeling schemesspace-time tradeoffs

Mathematics Subject Classification ID

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

Related Items (4)

Proof-labeling schemes: broadcast, unicast and in between ⋮ Lower bound for constant-size local certification ⋮ Compact distributed certification of planar graphs ⋮ Local certification of graphs with bounded genus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast and compact self-stabilizing verification, computation, and fault detection of an MST
• Local stabilizer
• The local detection paradigm and its applications to self-stabilization
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Space-time tradeoffs for distributed verification
• Transient fault detectors
• Distributed verification of minimum spanning trees
• Randomized proof-labeling schemes
• Proof labeling schemes
• On Mobile Agent Verifiable Problems
• Minimizing the Number of Opinions for Fault-Tolerant Distributed Decision Using Well-Quasi Orderings
• Distributedly Testing Cycle-Freeness
• High-Probability Parallel Transitive-Closure Algorithms
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• Communication Complexity
• Distributed Verification and Hardness of Distributed Approximation
• Proof-Labeling Schemes: Broadcast, Unicast and in Between
• The Power of Distributed Verifiers in Interactive Proofs
• Interactive Distributed Proofs
• Memory-efficient and self-stabilizing network RESET (extended abstract)
• Towards a complexity theory for local distributed computing
• Probability and Computing
• Perfect failure detection with very few bits
• Approximate proof-labeling schemes

This page was built for publication: Redundancy in distributed proofs