TY - GEN

T1 - Compact Distributed Certification of Planar Graphs

AU - Feuilloley, Laurent

AU - Fraigniaud, Pierre

AU - Montealegre, Pedro

AU - Rapaport, Ivan

AU - Rémila, Éric

AU - Todinca, Ioan

N1 - Funding Information:
∗Additional support from MIPP and José Correa’s Amazon Research Award †Additional support from ANR project DESCARTES. ‡Additional support from CONICYT via PAI + Convocatoria Nacional Subvención a la Incorporación en la Academia Año 2017 + PAI77170068 and FONDECYT 11190482. §Additional support from CONICYT via PIA/Apoyo a Centros Científicos y Tecnológi-cos de Excelencia AFB 170001 and Fondecyt 1170021 ¶Additional support from IDEXLYON (project INDEPTH) within the Programme Investissements d’Avenir (ANR-16-IDEX-0005) and “Mathématiques de la Décision pour l’Ingénierie Physique et Sociale” (MODMAD) Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.
Funding Information:
support from MIPP and Jos? Correa's Amazon Research Award.
Publisher Copyright:
© 2020 ACM.

PY - 2020/7/31

Y1 - 2020/7/31

N2 - Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(log n) bits in n-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a proof-labeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no proof-labeling schemes - - in fact, even no locally checkable proofs - - for planarity using certificates on o(log n) bits.

AB - Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(log n) bits in n-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a proof-labeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no proof-labeling schemes - - in fact, even no locally checkable proofs - - for planarity using certificates on o(log n) bits.

KW - communication networks

KW - distributed graph algorithms

KW - fault-tolerance

UR - http://www.scopus.com/inward/record.url?scp=85090339501&partnerID=8YFLogxK

U2 - 10.1145/3382734.3404505

DO - 10.1145/3382734.3404505

M3 - Conference contribution

AN - SCOPUS:85090339501

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 319

EP - 328

BT - PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 39th Symposium on Principles of Distributed Computing, PODC 2020

Y2 - 3 August 2020 through 7 August 2020

ER -