Redundancy in Distributed Proofs

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

Distributed Computing
doi: 10.1007/s00446-020-00386-z


Open-access publisher's version ArXiv version
Conference version page


Distributed proofs are mechanisms that enable 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 objects 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 a 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.


This paper had a conference version at DISC 2018. The journal version is basically the same paper, but with all the proofs, and with an improved presentation.


I presented both this paper and the paper Local verification of global proofs at DISC 2018 in New Orleans. (That's why there is one set of slides for both.)

I also presented it at the ANR Descartes meeting at IRIF, in March 2018. Ami also presented the paper a couple of times.