Balliu, Alkida ;
D'Angelo, Gianlorenzo ;
Fraigniaud, Pierre ;
Olivetti, Dennis
What Can Be Verified Locally?
Abstract
We are considering distributed network computing, in which computing entities are connected by a network modeled as a connected graph. These entities are located at the nodes of the graph, and they exchange information by messagepassing along its edges. In this context, we are adopting the classical framework for local distributed decision, in which nodes must collectively decide whether their network configuration satisfies some given boolean predicate, by having each node interacting with the nodes in its vicinity only. A network configuration is accepted if and only if every node individually accepts. It is folklore that not every Turingdecidable network property (e.g., whether the network is planar) can be decided locally whenever the computing entities are Turing machines (TM). On the other hand, it is known that every Turingdecidable network property can be decided locally if nodes are running nondeterministic Turing machines (NTM). However, this holds only if the nodes have the ability to guess the identities of the nodes currently in the network. That is, for different sets of identities assigned to the nodes, the correct guesses of the nodes might be different. If one asks the nodes to use the same guess in the same network configuration even with different identity assignments, i.e., to perform identityoblivious guesses, then it is known that not every Turingdecidable network property can be decided locally.
In this paper, we show that every Turingdecidable network property can be decided locally if nodes are running alternating Turing machines (ATM), and this holds even if nodes are bounded to perform identityoblivious guesses. More specifically, we show that, for every network property, there is a local algorithm for ATMs, with at most 2 alternations, that decides that property. 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 level k contains those tasks solvable with ATMs with k 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 properties that are locally decidable with TMs, NTMs, and ATMs. Finally, we establish the existence of completeness results for each of these classes, using novel notions of local reduction.
BibTeX  Entry
@InProceedings{balliu_et_al:LIPIcs:2017:7025,
author = {Alkida Balliu and Gianlorenzo D'Angelo and Pierre Fraigniaud and Dennis Olivetti},
title = {{What Can Be Verified Locallyl}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {8:18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7025},
URN = {urn:nbn:de:0030drops70253},
doi = {10.4230/LIPIcs.STACS.2017.8},
annote = {Keywords: Distributed Network Computing, Distributed Algorithm, Distributed Decision, Locality}
}
2017
Keywords: 

Distributed Network Computing, Distributed Algorithm, Distributed Decision, Locality 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

2017 