Redundancy in Distributed Proofs

Abstract : Distributed proofs are mechanisms enabling the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g. having a specific diameter), or on data structures distributed over the nodes (e.g. a spanning tree). We consider well known mechanisms consisting of two components: a prover that assigns a certificate to each node, and a distributed algorithm called verifier that is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between the size of the certificate stored at every node, and the number of rounds of the verification protocol.
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/hal-01964771
Contributor : Pierre Fraigniaud <>
Submitted on : Sunday, December 23, 2018 - 3:37:06 PM
Last modification on : Friday, September 6, 2019 - 10:36:02 PM
Long-term archiving on : Sunday, March 24, 2019 - 1:30:25 PM

File

tPLS-united_file.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, Mor Perry. Redundancy in Distributed Proofs. 32nd International Symposium on Distributed Computing, 2018, New Orleans, United States. ⟨10.4230/LIPIcs.DISC.2018.24⟩. ⟨hal-01964771⟩

Share

Metrics

Record views

26

Files downloads

18