A Meta-Theorem for Distributed Certification

Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

1 Cita (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaStructural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings
EditoresMerav Parter
EditorialSpringer Science and Business Media Deutschland GmbH
Páginas116-134
Número de páginas19
ISBN (versión impresa)9783031099922
DOI
EstadoPublicada - 2022
Publicado de forma externa
Evento29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022 - Paderborn, Alemania
Duración: 27 jun. 202229 jun. 2022

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen13298 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022
País/TerritorioAlemania
CiudadPaderborn
Período27/06/2229/06/22

Huella

Profundice en los temas de investigación de 'A Meta-Theorem for Distributed Certification'. En conjunto forman una huella única.

Citar esto