What Can Be Verified Locally?

Abstract : In the framework of distributed network computing, it is known that not all Turing-decidable predicates on labeled networks can be decided locally whenever the computing entities are Turing machines (TM), and this holds even if nodes are running non-deterministic Turing machines (NTM). In contrast, we show that every Turing-decidable predicate on labeled networks can be decided locally if nodes are running alternating Turing machines (ATM). More specifically, we show that, for every such predicate, there is a local algorithm for ATMs, with at most two alternations, that decides whether the actual labeled network satisfies that predicate. To this aim, we define a hierarchy of classes of decision tasks, where the lowest level contains tasks solvable with TMs, the first level those solvable with NTMs, and the level k > 1 contains those tasks solvable with ATMs with k − 1 alternations. We characterize the entire hierarchy, and show that it collapses in the second level. In addition, we show separation results between the classes of network predicates that are locally decidable with TMs, NTMs, and ATMs, and we establish the existence of completeness results for each of these classes, using novel notions of local reduction. We complete these results by a study of the local decision hierarchy when certificates are bounded to be of logarithmic size. * A preliminary version of this paper has appeared
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01964764
Contributor : Pierre Fraigniaud <>
Submitted on : Sunday, December 23, 2018 - 3:20:51 PM
Last modification on : Friday, January 4, 2019 - 5:33:38 PM
Long-term archiving on : Sunday, March 24, 2019 - 1:13:40 PM

File

revised-version2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01964764, version 1

Collections

Citation

Alkida Balliu, Gianlorenzo D 'Angelo, Pierre Fraigniaud, Dennis Olivetti. What Can Be Verified Locally?. Journal of Computer and System Sciences, Elsevier, 2018. ⟨hal-01964764⟩

Share

Metrics

Record views

118

Files downloads

104