Brief Announcement: Space–Time Tradeoffs for Distributed Verification
Mor Baruch, Rafail Ostrovsky, Will Rosenbaum
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 context of proof labeling schemes (P LS) [12], locally checkable proofs (LCP) [10], and non–deterministic local decision (NLD) [8]. In all of these contexts, verification time is assumed to be constant. Korman Kutten and Masuzawa [11] 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. label size, message length, and computation space. We construct a universalt–PLS and prove that t uses the same amount of total communication as known one–round universal t–PLS, and t factor smaller lables. In addtion , we provide a general technique to prove lower bounds for space –time tradeoffs of t–PLS. We use this technique to show an optimal tradeoff for testing that network is acyclic (cycle free ). Our optimal t–PLS for acyclicity uses label size and computation space Ο(logn/t). We further describe a recursive Ο(log∗ n) space verifier for acyclicity which does not assume previous knowledge of the run–time t.
comment: PODC 2016 PP: 357–359
Fetch PDF file of the paper
| Back to Publications List |