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 remark- able 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

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch
• Notes: 32nd International Symposium on Distributed Computing (DISC 2018). - Wadern, 2018. - 24:1-24:18, ISBN: 978-3-95977-092-7

Contributors, Places and Time

• Event: Veröffentlichung
• (where): Freiburg
• (who): Universität
• (when): 2022
• Creator: Feuilloley, Laurent ; Fraigniaud, Pierre ; Hirvonen, Juho ; Paz, Ami ; Perry, Mor
• Contributor: Albert-Ludwigs-Universität Freiburg. Algorithms and Complexity

Further information

• DOI: 10.4230/LIPIcs.DISC.2018.24
• URN: urn:nbn:de:bsz:25-freidok-2263493
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 15.08.2025, 7:35 AM CEST