Redundancy in Distributed Proofs

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Date
2018-10-01
Major/Subject
Mcode
Degree programme
Language
en
Pages
18
1-18
Series
32nd International Symposium on Distributed Computing (DISC 2018), Leibniz International Proceedings in Informatics (LIPIcs), Volume 121
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.
Description
Keywords
distributed verification, distributed graph algorithms, proof-labeling schemes, space-time tradeoffs, non-determinism
Other note
Citation
Feuilloley , L , Fraigniaud , P , Hirvonen , J , Paz , A & Perry , M 2018 , Redundancy in Distributed Proofs . in U Schmid & J Hirvonen (eds) , 32nd International Symposium on Distributed Computing (DISC 2018) . Leibniz International Proceedings in Informatics (LIPIcs) , vol. 121 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , Dagstuhl, Germany , pp. 1-18 , International Symposium on Distributed Computing , New Orleans , Louisiana , United States , 15/10/2018 . https://doi.org/10.4230/LIPIcs.DISC.2018.24