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 -