License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.24
URN: urn:nbn:de:0030-drops-98139
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9813/
Go to the corresponding LIPIcs Volume Portal

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

Redundancy in Distributed Proofs

pdf-format:
LIPIcs-DISC-2018-24.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{feuilloley_et_al:LIPIcs:2018:9813,
  author =	{Laurent Feuilloley and Pierre Fraigniaud and Juho Hirvonen and Ami Paz and Mor Perry},
  title =	{{Redundancy in Distributed Proofs}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9813},
  URN =		{urn:nbn:de:0030-drops-98139},
  doi =		{10.4230/LIPIcs.DISC.2018.24},
  annote =	{Keywords: Distributed verification, Distributed graph algorithms, Proof-labeling schemes, Space-time tradeoffs, Non-determinism}
}

Keywords: Distributed verification, Distributed graph algorithms, Proof-labeling schemes, Space-time tradeoffs, Non-determinism
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI