Redundancy in distributed proofs
- PDF / 656,496 Bytes
- 20 Pages / 595.276 x 790.866 pts Page_size
- 94 Downloads / 211 Views
Redundancy in distributed proofs Laurent Feuilloley1 · Pierre Fraigniaud2 · Juho Hirvonen3 · Ami Paz4 · Mor Perry5 Received: 8 October 2019 / Accepted: 24 September 2020 © The Author(s) 2020
Abstract Distributed proofs are mechanisms that enable 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 objects 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 a 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 · Nondeterminism
1 Introduction 1.1 Context and objective In the context of distributed fault-tolerant computing in large scale networks, it is of the utmost importance that the computing nodes can perpetually check the correctness of distributed objects (e.g., spanning trees) encoded distributively over the An extended abstract of this work was presented in DISC 2018 [21].
B
Ami Paz [email protected] Laurent Feuilloley [email protected] Pierre Fraigniaud [email protected] Juho Hirvonen [email protected] Mor Perry [email protected]
1
Universidad de Chile, Santiago, Chile
2
IRIF, CNRS, Université de , Paris, France
3
Aalto University, Espoo, Finland
4
Faculty of Computer Science, University of Vienna, Vienna, Austria
5
Weizmann Institute of Science, Rehovot, Israel
network. Such objects can be the outcome of an algorithm that might be subject to failures, or be a-priori correctly given objects but subject to later corruption. There are several mechanisms for checking the correctness of distributed objects (see, e.g., [2,3,7,10–12]), and here we focus on one classical mechanism which is both simple and versatile, known as proof-labeling schemes [37], or as locally checkable proofs [30].1 Roughly, a proof-labeling scheme assigns certificates to each node of the network. These certificates can be viewed as forming a distributed proof of the actual object. The nodes are then in charge of collectively verifying the correctness of this proof. The requirements are in a way similar to those imposed on non-deterministic algorithms (e.g., the class NP), namely: (1) on correct structures, the assigned certificates must be accepted, in the sense that every node must accept its given certificate; (2) on corrupted structures, whatever certificates are given to the nodes, they must be rejected, in the sense that at least one node must reject its
Data Loading...
