License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.25
URN: urn:nbn:de:0030-drops-98146
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9814/
Go to the corresponding LIPIcs Volume Portal

Feuilloley, Laurent ; Hirvonen, Juho

Local Verification of Global Proofs

pdf-format:
LIPIcs-DISC-2018-25.pdf (0.5 MB)

Abstract

In this work we study the cost of local and global proofs on distributed verification. In this setting the nodes of a distributed system are provided with a nondeterministic proof for the correctness of the state of the system, and the nodes need to verify this proof by looking at only their local neighborhood in the system.
Previous works have studied the model where each node is given its own, possibly unique, part of the proof as input. The cost of a proof is the maximum size of an individual label. We compare this model to a model where each node has access to the same global proof, and the cost is the size of this global proof.
It is easy to see that a global proof can always include all of the local proofs, and every local proof can be a copy of the global proof. We show that there exists properties that exhibit these relative proof sizes, and also properties that are somewhere in between. In addition, we introduce a new lower bound technique and use it to prove a tight lower bound on the complexity of reversing distributed decision and establish a link between communication complexity and distributed proof complexity.

BibTeX - Entry

@InProceedings{feuilloley_et_al:LIPIcs:2018:9814,
  author =	{Laurent Feuilloley and Juho Hirvonen},
  title =	{{Local Verification of Global Proofs}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9814},
  URN =		{urn:nbn:de:0030-drops-98146},
  doi =		{10.4230/LIPIcs.DISC.2018.25},
  annote =	{Keywords: Proof-labeling schemes, distributed verification, non-determinism, local proofs}
}

Keywords: Proof-labeling schemes, distributed verification, non-determinism, local proofs
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

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