What Can Be Verified Locally?

Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, Dennis Olivetti

Research output: Contribution to journalArticleScientificpeer-review

13 Citations (Scopus)
91 Downloads (Pure)

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). 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.
Original languageEnglish
Pages (from-to)106-120
JournalJOURNAL OF COMPUTER AND SYSTEM SCIENCES
Volume97
DOIs
Publication statusPublished - 2018
MoE publication typeA1 Journal article-refereed

Keywords

  • Distributed computing
  • Decision problems
  • Local model

Fingerprint

Dive into the research topics of 'What Can Be Verified Locally?'. Together they form a unique fingerprint.

Cite this