A Meta-Theorem for Distributed Certification

Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

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

1 Scopus citations

Abstract

Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two properties are satisfied: completeness, i.e., for every legal instance, there is a certificate assignment leading all processes to accept, and soundness, i.e., for every illegal instance, and for every certificate assignment, at least one process rejects. The verification of the certificates must be fast, and the certificates themselves must be small. A large quantity of results have been produced in this framework, each aiming at designing a distributed certification mechanism for specific boolean predicates. This paper presents a “meta-theorem”, applying to many boolean predicates at once. Specifically, we prove that, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs, there exists a distributed certification mechanism using certificates on O(log2n) bits in n-node graphs of bounded treewidth, with a verification protocol involving a single round of communication between neighbors.

Original languageEnglish
Title of host publicationStructural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings
EditorsMerav Parter
PublisherSpringer Science and Business Media Deutschland GmbH
Pages116-134
Number of pages19
ISBN (Print)9783031099922
DOIs
StatePublished - 2022
Externally publishedYes
Event29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022 - Paderborn, Germany
Duration: 27 Jun 202229 Jun 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13298 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022
Country/TerritoryGermany
CityPaderborn
Period27/06/2229/06/22

Keywords

  • Distributed decision
  • Fault-tolerance
  • Locally checkable proof
  • Proof-labeling scheme

Fingerprint

Dive into the research topics of 'A Meta-Theorem for Distributed Certification'. Together they form a unique fingerprint.

Cite this