DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2024.1

Fully Local Succinct Distributed Arguments

Authors: Eden Aldema Tshuva and Rotem Oshman

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

Distributed certification is a proof system for detecting illegal network states or improper execution of distributed algorithms. A certification scheme consists of a proving algorithm, which assigns a certificate to each node, and a verification algorithm where nodes use these certificates to decide whether to accept or reject. The system must ensure that all nodes accept if and only if the network is in a legal state, adhering to the principles of completeness and soundness. The main goal is to design a scheme where the verification process is local and the certificates are succinct, while using as efficient as possible proving algorithm. In cryptographic proof systems, the soundness requirement is often relaxed to computational soundness, where soundness is guaranteed only against computationally bounded adversaries. Computationally sound proof systems are called arguments. Recently, Aldema Tshuva, Boyle, Cohen, Moran, and Oshman (TCC 2023) showed that succinct distributed arguments can be used to enable any polynomially bounded distributed algorithm to certify its execution with polylogarithmic-length certificates. However, their approach required a global communication phase, adding O(D) communication rounds in networks of diameter D, which limits its applicability to local algorithms. In this work, we give the first construction of a fully local succinct distributed argument system, where the prover and the verifier are both local. We show that a distributed algorithm that runs in R rounds, has polynomial local computation, and messages of B bits each can be compiled into a self-certifying algorithm that runs in R + polylog(n) rounds and sends messages of size B + polylog(n), with certificates of length polylog(n). This construction has several applications, including self-certification for local algorithms, ongoing certification of long-lived algorithms, and efficient local mending of the certificates when the network changes.

Cite as

Eden Aldema Tshuva and Rotem Oshman. Fully Local Succinct Distributed Arguments. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aldematshuva_et_al:LIPIcs.DISC.2024.1,
  author =	{Aldema Tshuva, Eden and Oshman, Rotem},
  title =	{{Fully Local Succinct Distributed Arguments}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.1},
  URN =		{urn:nbn:de:0030-drops-212662},
  doi =		{10.4230/LIPIcs.DISC.2024.1},
  annote =	{Keywords: distributed certification, proof labeling schemes, SNARG}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2023.27

On Polynomial Time Local Decision

Authors: Eden Aldema Tshuva and Rotem Oshman

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract

The field of distributed local decision studies the power of local network algorithms, where each network can see only its own local neighborhood, and must act based on this restricted information. Traditionally, the nodes of the network are assumed to have unbounded local computation power, and this makes the model incomparable with centralized notions of efficiency, namely, the classes 𝖯 and NP. In this work we seek to bridge this gap by studying local algorithms where the nodes are required to be computationally efficient: we introduce the classes PLD and NPLD of polynomial-time local decision and non-deterministic polynomial-time local decision, respectively, and compare them to the centralized complexity classes 𝖯 and NP, and to the distributed classes LD and NLD, which correspond to local deterministic and non-deterministic decision, respectively. We show that for deterministic algorithms, requiring both computational and distributed efficiency is likely to be more restrictive than either requirement alone: if the nodes do not know the network size, then PLD ⊊ LD ∩ 𝖯 holds unconditionally; if the network size is known to all nodes, then the same separation holds under a widely believed complexity assumption (UP ∩ coUP ≠ 𝖯). However, when nondeterminism is introduced, this distinction vanishes, and NPLD = NLD ∩ NP. To complete the picture, we extend the classes PLD and NPLD into a hierarchy akin to the centralized polynomial hierarchy, and we characterize its connections to the centralized polynomial hierarchy and to the distributed local decision hierarchy of Balliu, D'Angelo, Fraigniaud, and Olivetti.

Cite as

Eden Aldema Tshuva and Rotem Oshman. On Polynomial Time Local Decision. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aldematshuva_et_al:LIPIcs.OPODIS.2023.27,
  author =	{Aldema Tshuva, Eden and Oshman, Rotem},
  title =	{{On Polynomial Time Local Decision}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.27},
  URN =		{urn:nbn:de:0030-drops-195179},
  doi =		{10.4230/LIPIcs.OPODIS.2023.27},
  annote =	{Keywords: Local Decision, Polynomial-Time, LD, NLD}
}

Search Results

Documents authored by Aldema Tshuva, Eden

Fully Local Succinct Distributed Arguments

Abstract

Cite as

On Polynomial Time Local Decision

Abstract

Cite as

Thanks for your feedback!

Could not send message