Advertisement
Published in:
2017 | OriginalPaper | Chapter
Space-Time Tradeoffs for Distributed Verification
Authors : Rafail Ostrovsky, Mor Perry, Will Rosenbaum
Published in: Structural Information and Communication Complexity
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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 (\(\mathrm {PLS}\)), locally checkable proofs (\(\mathrm {LCP}\)), and non-deterministic local decision (\(\mathrm {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\text {-}\mathrm {PLS}\), which allows the verification procedure to run for super-constant time. Our work analyzes the tradeoffs of \(t\text {-}\mathrm {PLS}\) between time, label size, message length, and computation space. We construct a universal \(t\text {-}\mathrm {PLS}\) and prove that it uses the same amount of total communication as a known one-round universal \(\mathrm {PLS}\), and t factor smaller labels. In addition, we provide a general technique to prove lower bounds for space-time tradeoffs of \(t\text {-}\mathrm {PLS}\). We use this technique to show an optimal tradeoff for testing that a network is acyclic (cycle free). Our optimal \(t\text {-}\mathrm {PLS}\) for acyclicity uses label size and computation space \(O((\log n)/t)\). We further describe a recursive \(O(\log ^* n)\) space verifier for acyclicity which does not assume previous knowledge of the run-time t.