License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2021.21
URN: urn:nbn:de:0030-drops-157969
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15796/
Go to the corresponding LIPIcs Volume Portal

Fischer, Orr ; Oshman, Rotem ; Shamir, Dana

Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators

pdf-format:
LIPIcs-OPODIS-2021-21.pdf (0.8 MB)

Abstract

In distributed verification, our goal is to verify that the network configuration satisfies some desired property, using pre-computed information stored at each network node. This is formally modeled as a proof labeling scheme (PLS): a prover assigns to each node a certificate, and then the nodes exchange their certificates with their neighbors and decide whether to accept or reject the configuration. Subsequent work has shown that in some specific cases, allowing more rounds of communication - so that nodes can communicate further across the network - can yield shorter certificates, trading off the space required to store the certificate against the time required for verification. Such tradeoffs were previously known for trees, cycles, and grids, or for proof labeling schemes where all nodes receive the same certificate.
In this work we show that in large classes of graphs, every one-round PLS can be transformed into a multi-round PLS with shorter certificates. We give two constructions: given a 1-round PLS with certificates of ? bits, in graphs families with balanced edge separators of size s(n), we construct a t-round PLS with certificates of size Õ(? ⋅ s(n) / t), and in graph families with an excluded minor and maximum degree Δ, we construct a t-round PLS with certificates of size Õ(? ⋅ Δ / √t). Our constructions are explicit, and we use erasure codes to exploit the larger neighborhood viewed by each node in a t-round PLS.

BibTeX - Entry

@InProceedings{fischer_et_al:LIPIcs.OPODIS.2021.21,
  author =	{Fischer, Orr and Oshman, Rotem and Shamir, Dana},
  title =	{{Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15796},
  URN =		{urn:nbn:de:0030-drops-157969},
  doi =		{10.4230/LIPIcs.OPODIS.2021.21},
  annote =	{Keywords: proof-labeling schemes, space-time tradeoffs, families with excluded minor}
}

Keywords: proof-labeling schemes, space-time tradeoffs, families with excluded minor
Collection: 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Issue Date: 2022
Date of publication: 28.02.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI