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.
