Redundancy in Distributed Proofs

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

doi:10.4230/LIPIcs.DISC.2018.24

Redundancy in Distributed Proofs

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

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

76 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 language	English
Title of host publication	32nd International Symposium on Distributed Computing (DISC 2018)
Editors	Ulrich Schmid, Juho Hirvonen
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Chapter	24
Pages	1-18
Number of pages	18
ISBN (Electronic)	978-3-95977-092-7
DOIs	https://doi.org/10.4230/LIPIcs.DISC.2018.24
Publication status	Published - 1 Oct 2018
MoE publication type	A4 Conference publication
Event	International Symposium on Distributed Computing - New Orleans, United States Duration: 15 Oct 2018 → 19 Oct 2018 Conference number: 32 http://www.disc-conference.org/wp/disc2018/

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Volume	121
ISSN (Electronic)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Abbreviated title	DISC
Country/Territory	United States
City	New Orleans
Period	15/10/2018 → 19/10/2018
Internet address	http://www.disc-conference.org/wp/disc2018/

Keywords

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

Access to Document

10.4230/LIPIcs.DISC.2018.24

LIPIcs-DISC-2018-24Final published version, 559 KBLicence: CC BY

Cite this

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) (pp. 1-18). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 121). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2018.24

@inproceedings{eed2259791a845ddad85f208b102da09,

title = "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 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.",

keywords = "distributed verification, distributed graph algorithms, proof-labeling schemes, space-time tradeoffs, non-determinism",

author = "Laurent Feuilloley and Pierre Fraigniaud and Juho Hirvonen and Ami Paz and Mor Perry",

year = "2018",

month = oct,

day = "1",

doi = "10.4230/LIPIcs.DISC.2018.24",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--18",

editor = "Ulrich Schmid and Juho Hirvonen",

booktitle = "32nd International Symposium on Distributed Computing (DISC 2018)",

address = "Germany",

note = "International Symposium on Distributed Computing, DISC ; Conference date: 15-10-2018 Through 19-10-2018",

url = "http://www.disc-conference.org/wp/disc2018/",

}

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

Redundancy in Distributed Proofs. / Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho et al.
32nd International Symposium on Distributed Computing (DISC 2018). ed. / Ulrich Schmid; Juho Hirvonen. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. p. 1-18 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 121).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Redundancy in Distributed Proofs

AU - Feuilloley, Laurent

AU - Fraigniaud, Pierre

AU - Hirvonen, Juho

AU - Paz, Ami

AU - Perry, Mor

N1 - Conference code: 32

PY - 2018/10/1

Y1 - 2018/10/1

N2 - 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.

AB - 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.

KW - distributed verification

KW - distributed graph algorithms

KW - proof-labeling schemes

KW - space-time tradeoffs

KW - non-determinism

U2 - 10.4230/LIPIcs.DISC.2018.24

DO - 10.4230/LIPIcs.DISC.2018.24

M3 - Conference article in proceedings

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 18

BT - 32nd International Symposium on Distributed Computing (DISC 2018)

A2 - Schmid, Ulrich

A2 - Hirvonen, Juho

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl, Germany

T2 - International Symposium on Distributed Computing

Y2 - 15 October 2018 through 19 October 2018

ER -

Feuilloley L, Fraigniaud P, Hirvonen J, Paz A, Perry M. Redundancy in Distributed Proofs. In Schmid U, Hirvonen J, editors, 32nd International Symposium on Distributed Computing (DISC 2018). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2018. p. 1-18. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.DISC.2018.24

Redundancy in Distributed Proofs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this