Redundancy in Distributed Proofs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

13 Downloads (Pure)

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.
Original languageEnglish
Title of host publication32nd International Symposium on Distributed Computing (DISC 2018)
EditorsUlrich Schmid, Juho Hirvonen
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Chapter24
Pages1-18
Number of pages18
ISBN (Electronic)978-3-95977-092-7
DOIs
Publication statusPublished - 1 Oct 2018
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Distributed Computing - New Orleans, United States
Duration: 15 Oct 201819 Oct 2018
Conference number: 32
http://www.disc-conference.org/wp/disc2018/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Volume121
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
CountryUnited States
CityNew Orleans
Period15/10/201819/10/2018
Internet address

Keywords

  • distributed verification
  • distributed graph algorithms
  • proof-labeling schemes
  • space-time tradeoffs
  • non-determinism

Fingerprint

Dive into the research topics of 'Redundancy in Distributed Proofs'. Together they form a unique fingerprint.

Cite this