CS Forum: Alkida Balliu, Gran Sasso Science Institute (GSSI)

CS department's public guest lecture on 'What can be verified locally?'. The lecture is open to everyone free-of-charge.

Alkida Balliu
GSSI, L’Aquila, Italy

Host: Prof Jukka Suomela
Time: 14:15 (coffee at 14:00)
Venue: T5, CS building

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 work, 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.

Bio

I am a Ph.D. student in Computer Science at Gran Sasso Science Institute (GSSI), L’Aquila, Italy. I am a student of Prof. Pierre Fraigniaud, and since February 2016 I am visiting Institut de Recherche en Informatique Fondamentale (IRIF) at CNRS and Univ. Paris Diderot, where I have the opportunity to work with my supervisor and colleagues. I obtained my MSc in Computer Science from the University of Bologna, Italy, under the guidance of Prof. Ozalp Babaoglu. I am interested in different aspects of distributed algorithms.