Redundancy in distributed proofs

DOI10.4230/LIPICS.DISC.2018.24MaRDI QIDQ5090916zbMATH OpenFDO

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

Publication date 21 July 2022

zbMATH Keywords

non-determinismdistributed verificationdistributed graph algorithmsspace-time tradeoffsproof-labeling schemes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Specification and verification (program logics, model checking, etc.) (68Q60) Distributed algorithms (68W15)

Recommendations

• Redundancy in distributed proofs
• Local verification of global proofs
• Interactive distributed proofs
• scientific article; zbMATH DE number 6820307
• Compact distributed certification of planar graphs

Cites work

• scientific article; zbMATH DE number 6820307 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Approximate proof-labeling schemes
• Communication Complexity
• Decidability classes for mobile agents computing
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• Distributed verification of minimum spanning trees
• Distributedly testing cycle-freeness
• Error-sensitive proof-labeling schemes
• Interactive distributed proofs
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Local stabilizer
• Locally checkable proofs in distributed computing
• Minimizing the number of opinions for fault-tolerant distributed decision using well-quasi orderings
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Networks cannot compute their diameter in sublinear time
• On mobile agent verifiable problems
• Perfect failure detection with very few bits
• Proof labeling schemes
• Proof-labeling schemes: broadcast, unicast and in between
• Randomized proof-labeling schemes
• Survey of distributed decision
• The local detection paradigm and its applications to self-stabilization
• Towards a complexity theory for local distributed computing
• Transient fault detectors
• What can be verified locally?

Cited in

(4)

• A hierarchy of local decision
• Trade-offs in distributed interactive proofs
• Redundancy in distributed proofs
• Twenty-two new approximate proof labeling schemes

This page was built for publication: Redundancy in distributed proofs

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