Author name cluster

Ioannis Chatzigiannakis

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

TCS Journal 2013 Journal Article

The computational power of simple protocols for self-awareness on graphs

Ioannis Chatzigiannakis
Othon Michail
Stavros Nikolaou
Paul G. Spirakis

We explore the capability of a network of extremely limited computational entities to decide properties about itself or any of its subnetworks. We consider that the underlying network of the interacting entities (devices, agents, processes etc.) is modeled by an interaction graph that reflects the network’s connectivity. We examine the following two cases: First, we consider the case where the input graph is the whole interaction graph and second where it is some subgraph of the interaction graph given by some preprocessing on the network. In each case, we devise simple graph protocols that can decide properties of the input graph. The computational entities, that are called agents, are modeled as finite-state automata and run the same global graph protocol. Each protocol is a fixed size grammar, that is, its description is independent of the size (number of agents) of the network. This size is not known by the agents. We present two simple models (one for each case), the Graph Decision Mediated Population Protocol (GDMPP) and the Mediated Graph Protocol (MGP) models, similar to the Population Protocol model of Angluin et al. , where each network link (edge of the interaction graph) is characterized by a state taken from a finite set. This state can be used and updated during each interaction between the corresponding agents. We provide some example protocols and some interesting properties for the two models concerning the computability of graph languages in various settings (disconnected input graphs, stabilizing input graphs). We show that the computational power within the family of all (at least) weakly-connected input graphs is fairly restricted. Finally, we give an exact characterization of the class of graph languages decidable by the MGP model in the case of complete interaction graphs: it is equal to the class of graph languages decidable by a nondeterministic Turing Machine of linear space that receives its input graph by its adjacency matrix representation.

Details DOI

TCS Journal 2011 Journal Article

Mediated population protocols

Othon Michail
Ioannis Chatzigiannakis
Paul G. Spirakis

We extend here the Population Protocol (PP) model of Angluin et al. (2004, 2006) [2, 4] in order to model more powerful networks of resource-limited agents that are possibly mobile. The main feature of our extended model, called the Mediated Population Protocol (MPP) model, is to allow the edges of the interaction graph to have states that belong to a constant-size set. We then allow the protocol rules for pairwise interactions to modify the corresponding edge state. The descriptions of our protocols preserve both the uniformity and anonymity properties of PPs, that is, they do not depend on the size of the population and do not use unique identifiers. We focus on the computational power of the MPP model on complete interaction graphs and initially identical edges. We provide the following exact characterization of the class MPS of stably computable predicates: a predicate is in MPS iff it is symmetric and is in NSPACE ( n 2 ).

Details DOI

TCS Journal 2011 Journal Article

Passively mobile communicating machines that use restricted space

Ioannis Chatzigiannakis
Othon Michail
Stavros Nikolaou
Andreas Pavlogiannis
Paul G. Spirakis

We propose a new theoretical model for passively mobile wireless sensor networks, called P M, standing for passively mobile machines. The main modification w. r. t. the population protocol model (Angluin et al. , 2006) [30] is that agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on complete interaction graphs and define the complexity classes PMSPACE ( f ( n ) ) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O ( f ( n ) ) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O ( log n ) memory, and use it to provide an exact characterization of the classes PMSPACE ( f ( n ) ) when f ( n ) = Ω ( log n ): they are precisely the classes of all symmetric predicates in NSPACE ( n f ( n ) ). As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Ω ( log n ). We next explore the computability of the PM model when the protocols use o ( log log n ) space per machine and prove that SEM = PMSPACE ( f ( n ) ) when f ( n ) = o ( log log n ), where SEM denotes the class of the semilinear predicates. Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O ( log log n ).

Details DOI

MFCS Conference 2010 Conference Paper

All Symmetric Predicates in NSPACE ( n 2 ) Are Stably Computable by the Mediated Population Protocol Model

Ioannis Chatzigiannakis
Othon Michail
Stavros Nikolaou
Andreas Pavlogiannis
Paul G. Spirakis

Abstract This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges ( SMPP ). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE ( n 2 ). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE ( n 2 ).

Details

MFCS Conference 2009 Invited Paper

Recent Advances in Population Protocols

Ioannis Chatzigiannakis
Othon Michail
Paul G. Spirakis

Abstract The population protocol model (PP) proposed by Angluin et al. [2] describes sensor networks consisting of passively mobile finite-state agents. The agents sense their environment and communicate in pairs to carry out some computation on the sensed values. The mediated population protocol model (MPP) [13] extended the PP model by communication links equipped with a constant size buffer. The MPP model was proved in [13] to be stronger than the PP model. However, its most important contribution is that it provides us with the ability to devise optimizing protocols, approximation protocols and protocols that decide properties of the communication graph on which they run. The latter case, suggests a simplified model, the GDM model, that was formally defined and studied in [11]. GDM is a special case of MPP that captures MPP’s ability to decide properties of the communication graph. Here we survey recent advances in the area initiated by the proposal of the PP model and at the same time we provide new protocols, novel ideas and results.

Details