Abstract: We work on an extension of the Population Protocol model
of Angluin et al. [1] that allows edges of the communication graph, G, to
have states that belong to a constant size set. In this extension, the so
called Mediated Population Protocol model (MPP) [2,3], both uniformity
and anonymity are preserved.We here study a simplified version of MPP,
the Graph Decision Mediated Population Protocol model (GDM), in
order to capture MPP's ability to decide graphlanguages. We also prove
some first impossibility results both for weakly connected and possibly
disconnected communication graphs.
Abstract: We work on an extension of the Population Protocol model of Angluin et al. that allows edges of the communication graph, G, to have states that belong to a constant size set. In this extension, the so called Mediated Population Protocol model (MPP), both uniformity and anonymity are preserved. We here study a simplified version of MPP, the Graph Decision Mediated Population Protocol model (GDM), in order to capture MPP's ability to decide (stably compute) graphlanguages (sets of communication graphs). To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph language is undecidable if we allow disconnected communication graphs. As a result, we focus on studying the computational limits of the GDM model in (at least) weakly connected communication graphs only and give several examples of decidable graphlanguages in this case. To do so, we also prove that the class of decidable graphlanguages is closed under complement, union and intersection operations. Node and edge parity, bounded out-degree by a constant, existence of a node with more incoming than outgoing neighbors and existence of some directed path of length at least k=O(1) are some examples of properties whose decidability is proven. To prove the decidability of graphlanguages we provide protocols (GDMs) for them and exploit the closure results. Finally, we prove the existence of symmetry in two specific communication (sub)graphs which we believe is the first step towards the proof of impossibility results in the GDM model. In particular, we prove that there exists no GDM, whose states eventually stabilize, to decide whether G contains some directed cycle of length 2 (2-cycle).
Abstract: Wireless Sensor Networks (WSNs) constitute a recent and promising new
technology that is widely applicable. Due to the applicability of this
technology and its obvious importance for the modern distributed
computational world, the formal scientific foundation of its inherent laws
becomes essential. As a result, many new computational models for WSNs
have been proposed. Population Protocols (PPs) are a special category of
such systems. These are mainly identified by three distinctive
characteristics: the sensor nodes (agents) move passively, that is, they
cannot control the underlying mobility pattern, the available memory to
each agent is restricted, and the agents interact in pairs. It has been
proven that a predicate is computable by the PP model iff it is
semilinear. The class of semilinear predicates is a fairly small class. In
this work, our basic goal is to enhance the PP model in order to improve
the computational power. We first make the assumption that not only the
nodes but also the edges of the communication graph can store restricted
states. In a complete graph of n nodes it is like having added O(n2)
additional memory cells which are only read and written by the endpoints
of the corresponding edge. We prove that the new model, called Mediated
Population Protocol model, can operate as a distributed nondeterministic
Turing machine (TM) that uses all the available memory. The only
difference from a usual TM is that this one computes only symmetric
languages. More formally, we establish that a predicate is computable by
the new model iff it is symmetric and belongs to NSPACE(n2). Moreover, we
study the ability of the new model to decide graphlanguages (for general
graphs). The next step is to ignore the states of the edges and provide
another enhancement straight away from the PP model. The assumption now is
that the agents are multitape TMs equipped with infinite memory, that can
perform internal computation and interact with other agents, and we define
space-bounded computations. We call this the Passively mobile Machines
model. We prove that if each agent uses at most f(n) memory for f(n)={\`U}(log
n) then a predicate is computable iff it is symmetric and belongs to
NSPACE(nf(n)). We also show that this is not the case for f(n)=o(log n).
Based on these, we show that for f(n)={\`U}(log n) there exists a space
hierarchy like the one for classical symmetric TMs. We also show that the
latter is not the case for f(n)=o(loglog n), since here the corresponding
class collapses in the class of semilinear predicates and finally that for
f(n)={\`U}(loglog n) the class becomes a proper superset of semilinear
predicates. We leave open the problem of characterizing the classes for
f(n)={\`U}(loglog n) and f(n)=o(log n).
Abstract: We explore the capability of a network of extremely limited
computational entities to decide properties about any of its subnetworks.
We consider that the underlying network of the interacting
entities (devices, agents, processes etc.) is modeled by a complete in-
teraction graph and we devise simple graph protocols that can decide
properties of some input subgraph provided by some preprocessing on
the network. The agents are modeled as nite-state automata and run
the same global graph protocol. Each protocol is a xed 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 propose a simple
model, the Mediated Graph Protocol (MGP) model, similar to the Population
Protocol model of Angluin et al., in which each network link is
characterized by a state taken from a nite set. This state can be used
and updated during each interaction between the corresponding agents.
We provide some interesting properties of the MGP model among which
is the ability to decide properties on stabilizing (initially changing for a
nite number of steps) input graphs and we show that the MGP model
has the ability to decide properties of disconnected input graphs. We
show that the computational power within the connected components is
fairly restricted. Finally, we give an exact characterization of the class
GMGP, of graphlanguages decidable by the MGP model: it is equal
to the class of graphlanguages decidable by a nondeterministic Turing
Machine of linear space that receives its input graph by its adjacency
matrix representation.
Abstract: 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 graphlanguages 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 graphlanguages decidable by the MGP model in the case of complete interaction graphs: it is equal to the class of graphlanguages decidable by a nondeterministic Turing Machine of linear space that receives its input graph by its adjacency matrix representation.