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 remark- able 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
- Standort
-
Deutsche Nationalbibliothek Frankfurt am Main
- Umfang
-
Online-Ressource
- Sprache
-
Englisch
- Anmerkungen
-
32nd International Symposium on Distributed Computing (DISC 2018). - Wadern, 2018. - 24:1-24:18, ISBN: 978-3-95977-092-7
- Ereignis
-
Veröffentlichung
- (wo)
-
Freiburg
- (wer)
-
Universität
- (wann)
-
2022
- Urheber
-
Feuilloley, Laurent
Fraigniaud, Pierre
Hirvonen, Juho
Paz, Ami
Perry, Mor
- Beteiligte Personen und Organisationen
- DOI
-
10.4230/LIPIcs.DISC.2018.24
- URN
-
urn:nbn:de:bsz:25-freidok-2263493
- Rechteinformation
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Letzte Aktualisierung
-
25.03.2025, 13:46 MEZ
Datenpartner
Deutsche Nationalbibliothek. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Beteiligte
- Feuilloley, Laurent
- Fraigniaud, Pierre
- Hirvonen, Juho
- Paz, Ami
- Perry, Mor
- Albert-Ludwigs-Universität Freiburg. Algorithms and Complexity
- Universität
Entstanden
- 2022
Ähnliche Objekte (12)
Non-clausal redundancy properties
Encoding Redundancy for Satisfaction-Driven Clause Learning
Local verification of global proofs
Local redundancy in SAT: generalizations of blocked clauses
Distributed redundancy in elastostatics for the design of adaptive structures
Clausal proofs for pseudo-boolean reasoning
Commutativity simplifies proofs of parameterized programs
Time redundancy
Scalable error isolation for distributed systems: modeling, correctness proofs, and additional experiments
Scalable error isolation for distributed systems: modeling, correctness proofs, and additional experiments
CRC (Cyclic Redundancy Check)
Enhanced Robot Compliance, State Estimation and Identification using Distributed Tactile Feedback: Leveraging Redundancy and Multimodality
Non-clausal redundancy properties
Encoding Redundancy for Satisfaction-Driven Clause Learning
Local verification of global proofs
Local redundancy in SAT: generalizations of blocked clauses
Distributed redundancy in elastostatics for the design of adaptive structures
Clausal proofs for pseudo-boolean reasoning
Commutativity simplifies proofs of parameterized programs
Time redundancy
Scalable error isolation for distributed systems: modeling, correctness proofs, and additional experiments
Scalable error isolation for distributed systems: modeling, correctness proofs, and additional experiments
CRC (Cyclic Redundancy Check)
Enhanced Robot Compliance, State Estimation and Identification using Distributed Tactile Feedback: Leveraging Redundancy and Multimodality
Non-clausal redundancy properties
Encoding Redundancy for Satisfaction-Driven Clause Learning
Local verification of global proofs
Local redundancy in SAT: generalizations of blocked clauses
Distributed redundancy in elastostatics for the design of adaptive structures
Clausal proofs for pseudo-boolean reasoning
Commutativity simplifies proofs of parameterized programs
Time redundancy
Scalable error isolation for distributed systems: modeling, correctness proofs, and additional experiments
Scalable error isolation for distributed systems: modeling, correctness proofs, and additional experiments
CRC (Cyclic Redundancy Check)