License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.8
URN: urn:nbn:de:0030-drops-70253
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7025/
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 message-passing 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 Turing-decidable 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 Turing-decidable network property can be decided locally if nodes are running non-deterministic 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 identity-oblivious guesses, then it is known that not every Turing-decidable network property can be decided locally.
In this paper, we show that every Turing-decidable network property can be decided locally if nodes are running alternating Turing machines (ATM), and this holds even if nodes are bounded to perform identity-oblivious 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:1--8:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-028-6},
ISSN = {1868-8969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte ValleĢe},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7025},
URN = {urn:nbn:de:0030-drops-70253},
doi = {10.4230/LIPIcs.STACS.2017.8},
annote = {Keywords: Distributed Network Computing, Distributed Algorithm, Distributed Decision, Locality}
}
|
Keywords: |
|
Distributed Network Computing, Distributed Algorithm, Distributed Decision, Locality |
|
Collection: |
|
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
06.03.2017 |
