Redundancy in distributed proofs

DOI10.4230/LIPICS.DISC.2018.24zbMATH Open1497.68297MaRDI QIDQ5090916FDOQ5090916

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

Publication date: 21 July 2022

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

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)

Cites Work

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

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)