Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Remila, E., & Todinca, I. (2021). Compact Distributed Certification of Planar Graphs. Algorithmica, 83(7), 2215–2244.
Abstract: Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), pp 1096-115, 2020. https://doi.org/10.1137/1.9781611975994.67) 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 with 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.
|
Goles, E., Leal, L., Montealegre, P., Rapaport, I., & Rios-Wilson, M. (2023). Distributed maximal independent set computation driven by finite-state dynamics. Int. J. Parallel Emergent Distrib. Syst., Early Access.
Abstract: A Maximal Independent Set (MIS) is an inclusion maximal set of pairwise non-adjacent vertices. The computation of an MIS is one of the core problems in distributed computing. In this article, we introduce and analyze a finite-state distributed randomized algorithm for computing a Maximal Independent Set (MIS) on arbitrary undirected graphs. Our algorithm is self-stabilizing (reaches a correct output on any initial configuration) and can be implemented on systems with very scarce conditions. We analyze the convergence time of the proposed algorithm, showing that in many cases the algorithm converges in logarithmic time with high probability.
|
