**
Space-Time Tradeoffs for Distributed Verification
**

**
**
*
Rafail Ostrovsky, Mor Perry, Will Rosenbaum
*

Verifying that a network configuration satisfies a given boolean predicate is a fundamental problem in distributed computing.
Many variations of this problem have been studied, for example in the context of proof labeling schemes (**PLS**), locally checkable proofs (**LCP**),
and non-deterministic local decision (**NLD**). In all of these contexts, verification time is assumed to be constant Korman et al. [16] presented a proof-labeling scheme for MST,
with poly-logarithmic verification time and logarithmic memory at each vertex.

In this paper we introduce the notion of a t-**PLS**,
which allows the verification procedure to run for super-constant time.
Our work analyzes the tradeoffs of t-**PLS** between time, lable size, message length, and computation space.
we construct a universal t-**PLS **and prove that is uses the same amount of total communication as known one-round universal **PLS**, and t factor smaller tables.
In addition, we provide a general technique to prove lower bounds for space-tme tradeoffs of t-**PLS**. We use this technique to show an optimal tradoff for testing that a network is acyclic ( cycle free).
Our optimal
t-PLS for acyclicity uses label size and computation space Ο)log n)/t). We further describe a recursive Ο(log^{∗}n) Space verifier for acyclicity which does not assume previous knowledge of the run-time t.

**comment:**
SIROCCO 2017: 53-70

Fetch PDF file of the paper

Back to Publications List |