Computation in networks of passively mobile finite-state sensors.
We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size. With a fairness condition on interactions, we define the concept of stable computation of a function or predicate, and give protocols that stably compute functions in a class including Boolean combinations of threshold-k, parity, majority, and simple arithmetic. We prove that all stably computable predicates are in NL. With uniform random sampling of pairs to interact, we define the model of conjugating automata and show that any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a protocol in a population of size n. We prove that all predicates computable with high probability in this model are in P  RL. Several open problems and promising future directions are discussed.
works]: Network Architecture and Design-distributed net-
works, network communications, network topology, wireless
communication; F.1.1 [Computation by Abstract De-
vices]: Models of Computation; F.1.2 [Computation by
# Supported in part by NSF grants CCR-9820888, CCR-
0098078, CSE-0081823, CNS-0305258, and by ONR grant
N00014-01-1-0795.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
July 25-28, 2004, St. John's, Newfoundland, Canada.

Abstract

Devices]: Modes of Computation-parallelism
and concurrency, probabilistic computation; E.1 [Data]: Data
Structures-distributed data structures
General Terms
Theory, Algorithms, Performance
Keywords
Di#use computation, finite-state agent, intermittent com-
munication, mobile agent, sensor net, stable computation
1. SCENARIO: A FLOCK OF BIRDS
Suppose we have equipped each bird in a particular flock
with a sensor that can determine whether the bird's temperature
is elevated or not, and we wish to know whether
at least 5 birds in the flock have elevated temperatures. We
assume that the sensors are quite limited: each sensor has
a constant number of bits of memory and can respond to a
global start signal, and two sensors can communicate only
when they are su#ciently close to each other.
In this scenario, the sensors are mobile, but have no control
over how they move, that is, they are passively mo-
bile. Initially, we assume that the underlying pattern of
movement guarantees a fairness condition on the interac-
tions: every pair of birds in the flock repeatedly come su#-
ciently close to each other for their sensors to communicate.
Under these assumptions, there is a simple protocol ensuring
that every sensor eventually contains the correct answer.
At the global start signal, each sensor makes a measurement,
resulting in a 1 (elevated temperature) or 0 (not elevated
temperature) in a counter that can hold values from 0 to 4.
When two sensors communicate, one of them sets its counter
to the sum of the two counters, and the other one sets its
counter to 0. If two counters ever sum to at least 5, the
sensors go into a special alert state, which is then copied by
every sensor that encounters them. The output of a sensor
is 0 if it is not in the alert state, and 1 if it is in the alert
state. If we wait a su#cient interval after we issue the global
start signal, we can retrieve the correct answer from any of
the sensors.
Now consider the question of whether at least 5% of the
birds in the flock have elevated temperatures. Is there a
protocol to answer this question in the same sense, without
assumptions about the size of the flock? In Section 3, we
show that such a protocol exists. More generally, we are interested
in fundamental questions about the computational
power of this and related models of interactions among members
of a distributed population of finite-state agents.
2. A WIDER VIEW
Most work in distributed algorithms assumes that agents
in a system are computationally powerful, capable of storing
non-trivial amounts of data and carrying out complex
calculations. But in systems consisting of massive amounts
of cheap, bulk-produced hardware, or of small mobile agents
that are tightly constrained by the systems they run on, the
resources available at each agent may be severely limited.
Such limitations are not crippling if the system designer has
fine control over the interactions between agents; even finite-state
agents can be regimented into cellular automata with
computational power equivalent to linear space Turing ma-
chines. But if the system designer cannot control these in-
teractions, it is not clear what the computational limits are.
Sensor networks are a prime example of this phenomenon.
Each sensing unit is a self-contained physical package including
its own power supply, processor and memory, wireless
communication capability, and one or more sensors capable
of recording information about the local environment of the
unit. Constraints on cost and size translate into severe limitations
on power, storage, processing, and communication.
Sensing units are designed to be deployed in large groups,
using local low-power wireless communication between units
to transmit information from the sensors back to a base station
or central monitoring site.
Research in sensor networks has begun to explore the possibilities
for using distributed computation capabilities of
networks of sensors in novel ways to reduce communication
costs. Aggregation operations, such as count, sum, average,
extrema, median, or histogram, may be performed on the
sensor data in the network as it is being relayed to the base
station [12, 13]. Flexible groups of sensors associated with
targets in spatial target tracking can conserve resources in
inactive portions of the tracking area [7, 17]. Though sensors
are usually assumed to be stationary or nearly so, permitting
strategies based on relatively stable routing, this assumption
is not universal in the sensor-network literature. For
example, an assumption of random mobility and packet relay
dramatically increases the throughput possible for communication
between source-destination pairs in a wireless
network [9].
The flock of birds scenario illustrates the question of characterizing
what computations are possible in a cooperative
network of passively mobile finite-state sensors. The assumptions
we make about the motion of the sensors are
that it is passive (not under the control of the sensors), sufficiently
rapid and unpredictable for stable routing strategies
to be infeasible, and that each pair of sensors will repeatedly
be close enough to communicate using a low-power wireless
signal.
There is a global start signal transmitted by the base station
to all the sensors simultaneously to initiate a computa-
tion. When they receive the global start signal, the sensors
take a reading (one of a finite number of possible input val-
ues) and attempt to compute some function or predicate
of all the sensor values. This provides a "snapshot" of the
sensor values, rather than the continuous stream of sensor
values more commonly considered. Sensors communicate in
pairs and do not have unique identifiers; thus, they update
their states based strictly on the pair of their current states
and on the role each plays in the interaction-one acting as
initiator and the other as responder.
In Section 3, we define a model of computation by pairwise
interactions in a population of identical finite-state agents.
Assuming a fairness condition on interactions, we define the
concept of stable computation of a function or predicate
by a population protocol. In Section 4, we consider the
question of what predicates can be stably computed when
interactions can occur between all pairs of agents. We give
protocols for threshold-k, parity, majority, and simple arithmetic
functions, as well as closure results that allow us to
define a useful expression language that captures a subset
of the power of this model. We also show that every predicate
computable in this model is in nondeterministic log
space. An open problem is to give an exact characterization
of the computational power of stable computation in this
model. In Section 5, we show that the all-pairs case is the
weakest for stably computing predicates by showing that it
can be simulated by any population that cannot be separated
into non-interacting subpopulations. The questions of
what additional predicates can be computed for reasonable
restrictions on the interactions and what properties of the
underlying interaction graph can be stably computed by a
population are open.
In Section 6, we obtain the model of conjugating automata
by adding a uniform sampling condition on interactions to
the assumption that interactions are enabled between all
pairs of agents. This allows us to consider computations
that are correct with high probability and to address questions
of expected resource use. We show that this model
has su#cient power to simulate, with high probability, a
counter machine with O(1) counters of capacity O(n). We
further show that Boolean predicates computable with high
probability in this model are in P # RL. This gives a partial
characterization of the set of predicates computable by
such machines, but finding an exact characterization is still
open. In Section 7, we describe other related work, and in
Section 8 we discuss some of the many intriguing questions
raised by these models.
3. A FORMAL MODEL
We define a model that generalizes the flock of birds scenario
from Section 1.
3.1 Population Protocols
A population protocol A consists of finite input and
output alphabets X and Y , a finite set of states Q, an
input function I : X # Q mapping inputs to states, an
output function O mapping states to outputs,
and a transition function
of states. If #(p,
transition, and we define #1 (p,
As a simple illustration, we formalize a version of the
count-to-five protocol from Section 1. The six states are
q0 , . , q5 . The input and output alphabets are
{0, 1}. The input function I maps 0 to q0 and 1 to q1 . The
output function O maps all states except q5 to 0 and the
state q5 to 1. The transition function #(q i , q j ) is defined as
then the result is (q5 , q5
then the result is (q i+j , q0 ).
A population protocol runs in a population of any finite
size n. A population P consists of a set A of n agents
together with an irreflexive relation E # A - A that we
interpret as the directed edges of an interaction graph.
E describes which agents may interact during the computa-
tion. Intuitively, an edge (u, v) # E means that u and v are
able to interact, with u playing the role of initiator and
v playing the role of responder in the interaction. Note
that the distinct roles of the two agents in an interaction
is a fundamental assumption of asymmetry in our model;
symmetry-breaking therefore does not arise as a problem
within the model. Though most of the present paper concerns
the case in which E consists of all ordered pairs of
distinct elements from A, we give definitions appropriate
for general E.
A population configuration is a mapping C : A # Q
specifying the state of each member of the population. Let C
and C # be population configurations, and let u, v be distinct
agents. We say that C goes to C # via encounter
denoted C e
We say that C can go to C # in one step, denoted C # C # , if
is a sequence of configurations
such that C i # C i+1 for all i, 0 # i < k, in which case we
say that C # is reachable from C.
A computation is a finite or infinite sequence of population
configurations C0 , C1 , C2 , . such that for each i,
computation is fair if for every pair
of population configurations C and C # such that C # C # ,
if C occurs infinitely often in the computation, then C # also
occurs infinitely often in the computation.
3.2 Computation by Population Protocols
As with nondeterministic Turing machines, we define a notion
of input and output, and we capture the input-output
behavior of population protocols by relations. Unlike Turing
machines, population protocols do not halt, so there is
no obvious fixed time at which to view the output of the
population. Rather, we say that the output of the computation
stabilizes if it reaches a point after which no agent can
subsequently change its output value, no matter how the
computation proceeds thereafter. Stability is a global property
of the population configuration, so individual agents
in general do not know when stability has been reached.
However, with suitable stochastic assumptions on the rate
at which interactions occur, it is possible to bound the expected
number of interactions until the output stabilizes.
We explore this approach in Section 6.
An input assignment is a function x : A # X and
describes the inputs to a population protocol. We let
X A denote the set of all input assignments. The inputs are
represented by an input configuration Cx , where
I(x(w)) for all w # A. We naturally extend I to a mapping
from input assignments to configurations by writing
Cx . In words, if x assigns input symbol # to agent u, then
agent u's state in configuration I(x) is I(#).
An output assignment is a function y : A # Y and describes
the outputs of a population protocol. We let
denote the set of all output assignments. Given a configuration
C, we let yC denote the corresponding output assign-
ment, where yC A. We naturally
extend O to a mapping from configurations to output assignments
by writing In words, if agent u is in
state q in configuration C, then agent u's output symbol in
output assignment O(C) is O(q).
A configuration C is said to be output-stable if O(C #
O(C) for all C # reachable from C. Note that we do not require
that only that their outputs be equal. An
infinite computation output-stabilizes if it contains an
output-stable configuration C, in which case we say that
it stabilizes to output O(C). It is immediate that an
infinite computation stabilizes to at most one output.
The output of a finite computation is the output of its
last configuration. The output of an infinite computation
that stabilizes to output y is y; the output is undefined if
the computation does not stabilize to any output. Because
of the nondeterminism inherent in the choice of encounters,
the same initial configuration may lead to di#erent computations
that stabilize to di#erent outputs.
A population protocol A running in a population P stably
computes an input-output relation RA as follows.
For each x # X and y # Y, RA(x, y) holds if and only if there
is a fair computation of A beginning in configuration I(x)
that stabilizes to output y. In the special case that RA is
single-valued 1 , we write say that
A stably computes the partial function
Continuing our count-to-five illustration, assume that the
agents are u1 , . , u6 and the interaction graph is complete. 2
Let the input assignment x be described by the vector
(0, 1, 0, 1, 1, 1),
assigning input symbols to the agents u1 . , u6 in that or-
der. The corresponding input configuration is
which leads to the following possible computation:
The configurations reachable from the last one above are
those with five agents assigned q0 and one agent assigned
q4 , and the outputs of all of them are equal to
(0, 0, 0, 0, 0, 0).
Therefore, R((0, 1, 0, 1, 1, 1), (0, 0, 0, 0, 0, 0)) holds, where R
is the input-output relation computed by this protocol. In
fact, R is singled-valued, so we can write
A relation R is single-valued if #x#y#z(R(x,y)#R(x, z) #
An intersection graph is complete if (u, v) is a directed edge
for all agents u, v with u #= v.
In this example, we could have designed our protocol so
that the configurations themselves stopped changing, but
this illustrates the fact that we only require the outputs to
stop changing. In the next section, we show that the irrelevance
of agent identities to this computation is a general
phenomenon.
3.3 Functions on Other Domains
As defined in Section 3.2, population protocols compute
partial functions from X to Y. In order to use population
protocols to compute functions on other domains, we need
suitable input and output encoding conventions.
Functions with Multiple Arguments.
Let f be a function over domain X n . The agent-based
input convention assumes an ordered set of n agents and
gives the i th argument to the i th agent, 1 # i # n. Depending
on the interaction graph and output conventions,
the particular ordering chosen for the agents might or might
not a#ect the function computed.
Predicates on X .
A predicate on X can be regarded as a function from
X to {0, 1}. The predicate output convention assumes
and requires every agent to agree on the output.
A population protocol A stably computes a predicate if
and only if its input-output relation is single-valued and for
all input assignments x, if the predicate is true of x, then
FA (x) is the output assignment that maps every agent to
otherwise, FA(x) is the output assignment that maps every
agent to 0. The formal count-to-five protocol described
above stably computes the predicate of x that is true if and
only if x assigns 1 to at least 5 di#erent agents. This generalizes
easily to functions from X to the set of output symbols
we require the final outputs of all the agents to be equal
to the correct value of the function.
Integer Functions.
be a partial function on integer vectors.
Integer input and output values are represented di#usely
across the population rather than being stored locally by
individual agents. We describe an encoding convention that
can represent O(1) integers with absolute values bounded
by O(n) in a population protocol with n agents.
Let # be a set. (We will generally take # to be either X,
Y , or Q.) A k-place integer encoding convention over
# is a mapping # Z k . Thus, # associates a k-vector
of integers to each element of #. We extend # to a mapping
# A
by summing over all agents: for # A , we define
u#A
#(u)),
that is, # maps each agent to a k-vector, and we sum over
all agents to obtain the vector #) that is represented by
#.
An integer input k-vector is encoded by a k-place encoding
convention # X over the input set X. An integer output
#-vector is encoded by an #-place encoding convention # Y
over the output set Y . During internal computation, A can
maintain an m-vector encoded by # Q over the state set Q.
Using these encoding conventions, we say that A stably
computes f if the following conditions hold:
1. For every r # Z k in the domain of f , there exists x # X
such that # X
2. For every x # X , if # X (x) is in the domain of f then
there exists y # Y such that RA (x, y) holds.
3. For every x # X and y # Y, if RA (x, y) holds then
Note that A can stably compute integer function f even
though RA is not single valued. It might happen, for exam-
ple, that
but # Y
Example of an Integer Function.
We describe a population protocol to compute the function
the integer quotient of m and 3. We
let the input and output encoding
functions be the identity. Thus, an input assignment x
represents m if the number of agents assigned 1 is m, and
similarly for output assignments.
The states are ordered pairs (i, j) of integers such that
and the state encoding function
is also the identity. The input map I maps 1 to the state
(1, to the state (0, 0). The output map O maps
state (i, j) to j.
The transition function is defined as follows: if
and
other transitions are
defined to leave the pair of states unchanged. Transitions
of the first type can accumulate two 1's to a 2, but leave
the sum of the first coordinates of the states unchanged.
Transitions of the second type reduce the sum of the first
coordinates of the states by 3 and increase the sum of the
second coordinates by 1. Eventually, no more transitions of
the first type will be possible, and the sum of the second
coordinates will be the integer quotient of m and 3, as de-
sired. (If the output map were changed to the identity, this
protocol would compute the ordered pair consisting of the
remainder of m modulo 3 and the integer quotient of m and
3.)
4. ALL-PAIR INTERACTIONS
In this section, we restrict attention to populations in
which the interaction graph is complete. Under this assump-
tion, stably computable input-output relations are invariant
under renaming of the agents, that is, if # is a permutation
on A and RA (x, y), then RA (x#,y#). In the case of predi-
cates, the output assignment y is a constant function, which
implies that y and the output is determined by the
multiset of input symbols. Therefore the stably computable
predicates are symmetric.
Because population protocols depend only on the states
of agents, not on their names, we define a standard agent
set An = {1, . , n} of size n, and we let Pn be a population
of size n consisting of the complete interaction graph on An .
Let {fn} be a family of Boolean functions such that fn :
{0, 1} n
# {0, 1} for all n # 1. A population protocol A stably
computes the family {fn} if for every n # 1, when A
is run on population Pn , it stably computes the function fn ,
with the agent-based input convention (agent i gets the i-th
argument) and the predicate output convention (eventually
every agent agrees on the correct output). By the discussion
above, every stably computable family of Boolean functions
is symmetric.
More generally, we consider languages, that is, predicates
on X # , the set of all finite strings of input symbols. We say
that population protocol A stably computes L if for every
when A is run on population Pn , it stably computes
the characteristic function of L restricted to strings of
length n, with the agent-based input and predicate output
conventions. If L is stably computable, it contains every
permutation of each of its elements.
4.1 Stably Computable Predicates
We begin by considering what families of Boolean functions
are stably computable.
Closure Properties.
Let {fn} and {gn} be families of Boolean functions stably
computable by population protocols A and B. By complementing
the output map of A, the family of negations {f #
is stably computable. By complementing the input map of
A, the family of functions {hn}, where hn is equal to fn
with its inputs complemented, is stably computable. Product
constructions with A and B yield population protocols
that stably compute the conjunction or disjunction of the
outputs of {fn} and {gn}. Formally, we have:
Lemma 1. Let {fn} and {gn} be families of Boolean func-
tions. If {fn} and {gn} are stably computable, then so are
Thus, in addition to predicates such as "at least 5 ones"
we can compute predicates such as "fewer than 5 ones", "at
least 5 zeros", "at most 5 zeros", "exactly 5 ones", "exactly
5, 7 or 9 ones" and so on. Though it is not immediately
obvious, parity and majority are also stably computable by
population protocols.
Parity.
The value of parity is 1 if there are an odd number of 1's
in the input, and 0 if there are an even number of 1's in the
input. Note that computing the parity function with the
predicate output convention is di#erent from computing the
remainder modulo 2 in the integer output encoding conven-
tion, because in the predicate output convention eventually
all the agents must have the correct output symbol.
Our construction for parity uses a state consisting of two
bits: the data bit and the live bit. Initially, the data bit is
equal to the input bit, and the live bit is 1. For each state,
the output bit is equal to the data bit. When two agents
whose live bits are both 1, one sets its live bit to 0, and
the other sets its data bit to the mod 2 sum of their data
bits. When an agent with live bit 0 meets an agent with live
bit 1, the former copies the data bit of the latter.
In this protocol, the mod 2 sum of the product of the live
bit and the data bit over all the agents in the population is
invariant and equal to the mod 2 sum of the inputs. Even-
tually, exactly one agent has its live bit set to 1. At that
point, its data bit is the correct output. Once there is a
single live bit set to 1, eventually every other agent copies
the (correct) data bit from that agent.
The live bit ensures a tree-structured computation aggregating
the data bits, with the final result at the root of the
tree. This generalizes to the computation of the product
of all the input values in a commutative semigroup. Thus,
all the symmetric regular languages are stably computable,
e.g., deciding whether the number of 1's is
constants i and m.
Majority.
The value of the majority function is 1 if there are more
1's than 0's in the input; otherwise, it is 0.
The states of our protocol consist of a live bit and a
counter with values in the set {-1, 0, 1}. Initially, the live
bit is 1, and the counter is -1 if the input is 0 and 1 if the
input is 1. The output is 1 if the counter is 1; otherwise, it
is 0. When two agents with live bit equal to 1 meet, if the
sum of their counters is in the set {-1, 0, 1}, then both set
their counters to the sum, and one of the agents sets its live
bit to 0; otherwise, they do nothing. When an agent with
live bit equal to 0 meets an agent with live bit equal to 1,
the former copies the counter value of the latter.
In this protocol, the sum of the counters for all agents
with live bit equal to 1 is invariant and equal to the number
of 1's minus the number of 0's in the input. Eventually
there will remain one or more live bits equal to 1, with no
more combinations possible, which means that the associated
have a single value -1, 0, or 1, indicating
that the number of 1's in the input is less than, equal to,
or greater than the number of 0's in the input, respectively.
After this point, every other agent will copy the common
counter value, and their outputs will also be correct.
A generalization with counters capable of holding integer
values between -k and k inclusive determines whether at
least a fraction 1/(k+1) of the inputs are 1's, demonstrating
the existence of a population protocol to detect whether at
least 5% of the flock of birds have elevated temperatures, as
claimed in Section 1.
Arithmetic Functions.
Recall from Section 3.3 the distributed representation of
O(1) integers of absolute value O(n) and the example of
the protocol to divide by 3. Using similar encodings and
ideas, there are population protocols to compute the sum of
two integers, the product of an integer and a constant, the
integer quotient of an integer and a constant, the value of an
integer modulo a constant, and a constant function (equal
to k for all inputs). Given stable inputs, these protocols
output-stabilize and thus can be composed freely.
A Stably Computable Expression Language.
Putting together the base functions and closure results, we
can define an expression language such that the expressible
predicates are stably computable by population protocols.
This gives a lower bound on the set of stably computable
predicates: whether every stably computable predicate is so
expressible is an open problem.
Expressions are defined as follows. For each input symbol
# X, there is a variable N# representing the number
of agents assigned the symbol # by the input assignment.
Constants are nonnegative integers. Each term is a con-
stant, a variable, or the sum of two terms, or the product of
a constant and a term, or the integer quotient of a term and
a nonzero constant, or the remainder of a term modulo a
nonzero constant. Atomic expressions are formed from two
terms and one of the predicates: =, #, >. An expression
is either an atomic expression or the negation of an
expression, the conjunction of two expressions, or the disjunction
of two expressions. Each expression is either true
or false of a given input assignment, by the usual semantics.
For example, the count-to-five problem is expressible as
5), the parity problem as ((N1 mod 1), and the
majority problem as (N1 > N0 ). The question of whether
the number of 1's is between 15% and 20% of the total population
can be expressed as
This idea extends to predicates on non-binary input alpha-
bets, so that if we can express the predicate
that the number of a's, b's, and c's are equal by the expression
Theorem 2. Any predicate expressed in the language described
above is stably computable.
(As already noted, whether the converse holds is an open
problem.)
Proof Sketch. Because the set of stably computable
predicates is closed under complementation, union, and in-
tersection, it su#ces to show that the terms and atomic
expressions of the language described above are stably computable

Given a term of the language, we use the distributed representation
of integers and allocate a component of the state
for each subterm of the expression, including variables and
constants. The input map places the value of N# into the
component allocated to it. For each other subterm of the
expression, there is a subprotocol (operating in parallel with
all the others) to compute its value in the correct component
of the state, generally as a function of the values being computed
in other components. These use the protocols for sum,
multiplication by a constant, division by a constant, and remainder
modulo a nonzero constant, and constant functions,
which each eventually stabilize to the correct outputs.
For atomic expressions, it su#ces to consider (t1 # t2 ),
again because the stably computable predicates are closed
under negation, intersection and union. We use the above
method of computing the values of all the subterms of this
expression, and run (also in parallel) a protocol to compare
the values of t1 and t2 and propagate the results to all other
agents. This protocol is similar to the majority protocol
described above.
We note in passing that there is an exact relationship
between our expression language and the semilinear sets.
Fix an ordering #1 , . , #k of the input alphabet, and define
the Parikh map # from X # to N k by
is the number of occurrences of # in x. Using
Ginsburg and Spanier's characterization of the semilinear
sets as those that can be defined in Presburger arithmetic [8],
it is straightforward (but beyond the scope of this paper) to
show that the semilinear sets in N k are precisely the images
under # of predicates expressible in the language defined
above. Thus, we may rephrase one of our open problems:
are there stably computable predicates whose corresponding
subsets of N k are not semilinear?
4.2 Predicates Not Stably Computable
Theorem 2 gives a partial characterization of the stably
computable predicates in the population model with all pairs
enabled. We do not know if this characterization is com-
plete. However, we can obtain an upper bound on the set of
predicates stably computable in this model by showing that
it is contained in the complexity class NL.
Because stably computable predicates in this model are
symmetric, it is su#cient to represent a population configuration
by the multiset of states assigned to the agents. Since
there are |Q| possible states and the population consists of
agents, each population configuration can thus be represented
by |Q| counters of #log n# bits each. A population
protocol step can be simulated by drawing two elements of
the multiset, applying the transition function and returning
the resulting two elements to the multiset.
If there is a population protocol A that stably computes
a language L # X # , then there is a nondeterministic Turing
machine to accept L in space O(log n). To accept input x,
the Turing machine must verify two conditions: that there
is a configuration C reachable from I(x) in which all states
have output 1, and there is no configuration C # reachable
from C in which some state has output 0. The first condition
is verified by guessing and checking a polynomial-length
sequence of multiset representations of population configurations
reaching such a C. The second condition is the complement
of a similar reachability condition. It is in nondeterministic
O(log n) space because this class is closed under
complement [11]. It follows that:
Theorem 3. All predicates stably computable in the model
with all pairs enabled are in the class NL.
It is an open problem to characterize exactly the power of
this model of stable computation. Concretely, we conjecture
that predicates such as "the number of 1's is a power of
2" and "the number of c's is the product of the number
of a's and the number of b's" are not stably computable
by population protocols. Our intuition is that the model
lacks the ability to sequence or iterate computations, and
we suspect that a pumping lemma of some form exists for
the model.
5. RESTRICTED INTERACTIONS
Some interaction graphs may permit very powerful computations
by population protocols; for example, a population
whose interaction graph is a directed line can easily
simulate a linear-space Turing machine. In this section, we
prove that the complete interaction graph we have been assuming
up until now is in a sense the weakest structure for
stably computing predicates, in that any weakly-connected
interaction graph can simulate it.
Theorem 4. For any population protocol A, there exists
a population protocol A # such that for every n, if A stably
computes predicate P on the standard population Pn , and
if P # is any population with agents 1,2,. ,n and a weakly-connected
interaction graph, then A # stably computes P on
Proof Sketch. The key idea is to have any interaction
in A # choose nondeterministically between swapping the
states of the two interacting agents-which eventually brings
any two simulated agents together-or simulating an inter-action
in A; most of the details of the simulation involve
implementing this nondeterministic choice with deterministic
transitions. To do so, the state space in A # is augmented
to add two "batons", S (for the initiator) and R (for respon-
der), which move somewhat independently of the simulated
agents. The presence or not of the two batons is used to
control what e#ect an interaction has: an interaction that
involves no batons swaps the states; an interaction that involves
one baton moves the baton; and an interaction that
involves both batons simulates a transition in A. This mechanism
assumes that n is at least 4 to give room to move the
batons out of the way; smaller n values are handled by a separate
protocol running in parallel that overrides the output
of the main protocol if it detects n # 3.
is the state space of
A, D is a default initial state of the baton field, S marks
the initiator baton, R marks the responder baton, and -
marks a "blank" or absent baton. Writing ordered pairs
in Q # using simple concatenation, e.g., qD for (q, D), the
transition function # is given by
where x and y range over all states in Q, # represents any
non-D baton, and
The first group of transitions consumes all initial D ba-
tons, producing at least one S and at least one R baton;
the second group eventually reduces the set of non-blank
batons to exactly one S and one R. The remaining groups
implement (a) baton movement, (b) state swapping, and (c)
A-transitions. Note that A-transitions also swap batons;
this is done to allow S and R batons to pass each other in
narrow graphs, which may be necessary to bring duplicates
together in the initial stage.
The simulated A execution is obtained by ignoring both
the batons and agent order. Most of the proof of correctness
involves showing that fairness holds in the simulation,
that is, that any state that is reachable infinitely often is
reached infinitely often. This is done by showing that any
A-transition can be simulated by a finite sequence of A # -
transitions, involving moving the relevant states to adjacent
agents using state swaps (which may require additional transitions
to move the batons o# each edge before the states on
its endpoints can be swapped), moving the S and R batons
onto the adjacent agents, and triggering an A-transition.
6. RANDOMIZED INTERACTIONS: CONJUGATING
"Stability" is probably not a strong enough guarantee for
most practical situations, but it is the best we can o#er given
only the fairness condition. To make stronger guarantees,
we must put some constraints on the interactions between
members of the population.
Let us add a probabilistic assumption on how the next pair
to interact is chosen. Many assumptions would be reason-able
to study. We consider one of the simplest: the ordered
pair to interact is chosen at random, independently and uniformly
from all ordered pairs corresponding to edges in the
interaction graph. When the interaction graph is complete,
this is the model of conjugating automata, inspired by
models introduced by Diamadi and Fischer to study the acquisition
and propagation of knowledge about trustworthiness
in populations of interacting agents [4].
Random pairing is su#cient to guarantee fairness with
probability 1, so any protocol that stably computes a predicate
g in a fair model computes g with probability 1 on every
input in the corresponding random-pairing model, assuming
both run on the same population.
However, probabilities also allow us to consider problems
where we only compute the correct answer with high prob-
ability, or to describe the expected number of interactions
until a protocol converges. Given a function f mapping X
to Y, a population protocol A, and an input x, we define the
probability that A computes f on input x to be the probability
of all computations beginning with I(x) that stabilize
with output f(x).
For example, for the parity protocol, the expected number
of interactions in a computation until there is just one live
bit equal to 1 is #(n 2 ), and the expected number of further
interactions until every other member of the population has
interacted with the unique member with live bit equal to 1 is
log n). Thus the expected total number of interactions
until the output is correct is #(n 2 log n). In general, we
are interested in protocols that accomplish their tasks in
an expected number of interactions polynomial in n, the
population size. 3
Generalizing this argument, we obtain the following by
structural induction:
Theorem 5. Let P be a predicate defined by the language
of Section 4.1. Then there is a randomized population protocol
that computes P with probability 1, where the population
converges to the correct answer in expected total number of
interactions O(kP n 2 log n), where kP is a constant depending
on P .
6.1 The Benefits of a Leader
Simulating Counters.
If we are allowed to designate a leader in the input con-
figuration, that is, one agent that starts in a distinguished
state, then the leader can organize the rest of the population
to simulate a counter machine with O(1) counters of capacity
O(n), with high probability. We assume throughout this
section that the interaction graph is complete.
We use the representation described in Section 3.3 for integers
in arithmetic computations. For a simulation of k
counters in which counter i can take on a maximum value of
n, each state is mapped to a k-tuple of nonnegative integers
in [0, c1 ] -[0, ck ]. The sum of component i over the
population gives the current contents of counter i. We assume
that the inputs to the counter machine are supplied in
designated counters and the leader simulates the finite-state
control of the counter machine.
3 Note that such protocols do not terminate with a final an-
they remain capable of resuming indefinitely.
To decrement counter i, the leader waits to encounter an
agent with component i of its state greater than zero, and
decrements it. Incrementing counter i is similar; component
i must be less than its maximum value c i . These operations
will happen with probability 1, assuming that they are pos-
sible. However, testing counter i for zero is di#erent; the
leader must attempt to decide whether there are any agents
with component i greater than zero. We give a method that
is correct with high probability. It is the ability to make
(possibly incorrect) decisions that enables e#ective sequencing
and iteration of computations in this model.
The leader initially labels one other agent (the timer) with
a special mark. The leader waits for one of two events: (1) an
interaction with an agent with a nonzero in component i, or
consecutive interactions with the timer. If an event of
type (1) occurs first, then the simulated counter is certainly
not zero. The event (2) has low probability, so if it occurs
first, the probability is high that the leader has encountered
every other agent in the meantime and may (with a small
probability of error) conclude that the value of simulated
counter i is zero. The parameter k controls the probability
of error, at the expense of increasing the expected number
of interactions.
Lemma 6. If the leader marks one other agent as a timer,
the expected total number of interactions until the leader encounters
the timer k times in a row is #(n k+1 ).
Proof Sketch. Let T (k) be the number of encounters
involving the leader until the leader encounters the timer k
times in a row. Then T
-T (k) because
the leader must first encounter the timer k-1 times in a row.
Once that happens, another agent is encountered by the
leader. With probability n-1
, it is not the timer, in which
case we must start all over again. Solving the recurrence
relation for T (k), we get T
expands to T
#(n k ). Since the probability
that the leader is involved in a given encounter is 2/n, the
result follows.
Rather than sum error bounds for individual counter op-
erations, we analyze the error associated with the macro-
operations on counters:
Lemma 7. For su#ciently large k, the operations of zeroing
a counter or zeroing a counter while adding its contents
to one or more other counters can be performed in an expected
total number of interactions #(n k+1 ) with O((1/n) k-1
log n) probability of error. The same holds for the operations
of multiplying by a constant, integer quotient with a
constant, or remainder modulo a constant.
Proof Sketch. We show the bounds on the number of
interactions and probability of error for zeroing counter i,
which is the fundamental operation. The leader marks one
other agent as a timer and waits for one of the following
two events: (1) an encounter with an agent with a non-zero
component i, in which case, the agent's component i is set to
zero, (2) k consecutive encounters with the timer, in which
case the leader concludes that the zeroing operation is com-
plete. The bound on the expected number of interactions
follows directly from Lemma 6.
To calculate the probability of error, note that a failure
occurs only if the leader encounters the timer k times in a
row before it encounters every agent with a nonzero component
be the probability that the leader encounters
the timer k - i times in a row given that m members of
the population have a nonzero component i. We want to
compute f0 . We do so by solving the recurrence
eventually deriving
which can be simplified to show that f0 < ( 1
/m. The
probability of error is bounded above by P n
which is in O((1/n) k-1
log n).
To achieve the other operations, we elaborate the zeroing
operation as follows: (1) increment each of a collection of
other counters for each decrement of the source counter, to
copy the source value to these destinations, (2) increment
another counter c times for each decrement of the source
counter, to multiply the source counter by c, (3) increment
another counter once for each c decrements of the source
counter, to divide the source counter by c and simultaneously
find its value modulo c. The analysis of interaction
and error bounds is similar.
How to Elect a Leader.
If we do not have a unique leader in the input configura-
tion, it is possible to establish one using the ideas of the live
bit, as in the parity and majority protocols of Section 4.1,
and the timer mark of Section 6.1.
At the global start signal, every agent receives its input
(which it remembers for the duration of the com-
putation), sets its live bit equal to 1, and clears its timer
mark (indicating that it is not a timer). Any agent whose
live bit equals 1 begins an initialization phase: it marks the
first non-timer agent that it encounters as a timer and attempts
to initialize every other agent. It uses the event of
encountering a timer k times in a row to determine the end
of the initialization phase.
Of course, at first every agent is attempting to run the initialization
phase, so there will be general chaos. Whenever
two agents with live bit equal to 1 encounter each other, one
(the loser) sets its live bit to 0, and the other (the winner)
keeps its live bit 1. If the loser has already marked a timer,
the winner waits until it encounters a timer and turns it
back into a non-timer before proceeding. The winner then
restarts the initialization phase (not creating another timer
if it has already released one). When initialized, agents with
live bit equal to 0 revert to a state representing only their
input and their live bit, but they retain their timer status.
If an agent with live bit equal to 1 completes the initialization
phase, it begins the computation (e.g., simulating
a counter machine, as in the preceding section). If during
the computation it encounters another agent with live bit
equal to 1, the two proceed as indicated above, one setting
its live bit to 0, and the other restarting the initialization
phase, with appropriate housekeeping to ensure retrieval of
the extra timer, if any.
After a period of unrest lasting an expected #(n 2 ) inter-
actions, there will be just one agent with live bit equal to
1. After the interaction eliminating the last rival, this lucky
winner will succeed in initializing all other agents with high
probability (because there is only one timer in the popu-
lation) and proceed with the computation as the unique
leader. If and when the counter machine halts, the unique
leader can propagate that fact (along with the output, if a
function of one output is being computed) to all the other
agents. If there have been no errors during the (final) sim-
ulation, the output of every configuration in the rest of the
computation is correct.
We have just shown how to carry out the operations of
a counter machine with high probability. Using a standard
construction due to Minsky [15], we can now simulate randomized
log-space Turing machines with high probability.
Corollary 8. Let f(x) be a function in randomized log-
space, where the input x is represented in unary. Then for
any fixed c, there is a population protocol that, with n mem-
bers, computes f(x) for any x # n with probability of error
O(n -c ) in expected time polynomial in n.
6.2 Simulating Randomized Population Protocol

In this section, we show either deterministic polynomial
time or randomized logarithmic space is su#cient to recognize
predicates computable with probability at least 1/2
by a population protocol with random pairing.
Suppose that a population protocol A computes a predicate
with probability at least 1/2 + #. Then P can be
computed by a polynomial-time Turing machine. As before,
we assume that a string x of symbols from X represents an
input assignment x to A, so that n represents both the input
length and the population size.
On input x, a polynomial-time Turing machine can construct
the matrix representing the Markov chain whose states
are the multiset representations of the population configurations
reachable from I(x), since there are at most n |Q| of
them. Solving for the stationary distribution of the states,
the Turing machine can determine a set of configurations of
probability greater than 1/2 that all have the same output
(which must be correct.) The Turing machine then writes
this common output to its output tape and halts.
Also under these assumptions, P can be computed by a
randomized Turing machine with probability 1/2 using
space O(log n). A randomized Turing machine simulates the
population protocol by using a finite number of O(log n)-bit
counters to keep track of the number of members of the population
in each state. Using coin flips, it simulates drawing a
random pair of population members and updating the counters
according to the transition function of A. By running
the simulation for long enough, the randomized Turing machine
can be almost certain of being in a terminal strongly
connected component of the states of the Markov chain, at
which point the Turing machine halts and writes the output
of the current configuration on its output tape.
To wait su#ciently long, the randomized Turing machine
allocates a counter of c#log n# bits and flips a coin before
each simulated interaction, adding 1 to the counter on heads,
and clearing the counter on tails. The simulation is stopped
when the counter overflows, that is, when there have been at
least n c consecutive heads. This gives an expected number
of simulated interactions before termination of at least 2 n c
We have just shown:
Theorem 9. The set of predicates accepted by a randomized
population protocol with probability 1/2 + # is contained
in P # RL.
7. OTHER RELATED WORK
In a Petri net, a finite collection of tokens may occupy
one of a finite set of places, and transition rules specify how
the tokens may move from place to place. 4 Viewing the
states of a population protocol as places, and the population
members as tokens, our models can also be interpreted as
particular kinds of Petri nets. Randomized Petri nets were
introduced by Volzer [16] using a transition rule that does
not depend on the number of tokens in each input place, as
ours does in the case of conjugating automata.
The Chemical Abstract Machine of Berry and Boudol [2] is
an abstract machine designed to model a situation in which
components move about a system and communicate when
they come into contact, based on a metaphor of molecules in
a solution governed by reaction rules. A concept of enforced
locality using membranes to confine subsolutions allows the
machines to implement classical process calculi or concurrent
generalizations of the lambda calculus.
Ibarra, Dang, and Egecioglu [10] consider a related model
of catalytic P systems. They show that purely catalytic systems
with one catalyst define precisely the semilinear sets,
and also explore other models equivalent in power to vector
addition systems. The relationships between these models
and ours is an intriguing topic.
Brand and Zafiropulo [3] define a model of communicating
processes consisting of a collection of finite state machines
that can communicate via pre-defined FIFO message
queues, and focus on general properties of protocols defined
in the model, such as the possibility of deadlock or loss of
synchronization.
Milner's bigraphical reactive systems [14] address the issues
of modeling locality and connectivity of agents by two
distinct graph structures. In this work the primary focus is
upon the expressiveness of the models, whereas we consider
issues of computational power and resource usage.
8. DISCUSSION AND OPEN PROBLEMS
In addition to the open problem of characterizing the
power of stable computation, many other intriguing questions
and directions are suggested by this work. One direction
we have explored [1] is to define a novel storage device,
the urn, which contains a multiset of tokens from a finite alphabet
and functions as auxiliary storage for a finite control
with input and output tapes, analogous to the pushdown or
work tape of traditional models. Access to the tokens in the
urn is by uniform random sampling, making it similar to the
model of conjugating automata.
We have primarily considered the case of a complete inter-action
graph, which we have shown in Theorem 9 provides
the least computational power of all weakly-connected inter-action
graphs in the stable computation model. The question
of characterizing the power of stable computations on
particular restricted interaction graphs remains open. We
can also consider the interaction graph itself as part of the
input and ask what interesting properties of its underlying
graph can be stably computed by a population protocol.
This problem may have applications in analyzing the structure
of deployed sensor networks.
An interesting restriction of our model is to consider only
one-way communication between the two agents in an in-
teraction, that is, the transition function # can be restricted
4 See [5, 6] for surveys of Petri nets.
to change only the state of the responder in the interaction,
keeping the state of the initiator the same. Although there
are still protocols to decide whether the number of 1's in
the input is at least k, this condition appears to restrict the
stably computable predicates severely.
The models in this paper assume a "snapshot" of the inputs
is taken when the global start signal is received. A
model accommodating streaming inputs, as is typically assumed
in sensor networks, would be very interesting.
We have assumed uniform sampling of pairs to interact,
but for some applications it may make sense to consider
other sampling rules. One idea is weighted sampling, in
which population members are sampled according to their
weights, possibly depending on their current states. We
conjecture that with reasonable restrictions on the weights,
weighted sampling yields the same power as uniform sam-
pling. Other sampling rules might be based on more accurate
models of patterns of interaction in populations of
interest.
The interaction rules we consider are deterministic and
specify pairwise interactions. What happens if the rules are
nondeterministic, or specify interactions of larger groups, or
allow the interaction to increase or decrease the population?
We give bounds on the expected total number of interac-
tions, but other resource measures may be more appropriate
in some applications. For many applications, interactions
happen in parallel, so that the total number of interactions
may not be well correlated with wall-clock time; defining
a useful notion of time is a challenge. Alternatively, if we
consider only the number of interactions in which at least
one state changes (which might be correlated with the energy
required by the computation), then the bounds can be
finite even in the stable computation model, and the expected
bounds can be smaller in the conjugating automata
model.
9.

ACKNOWLEDGMENTS

The authors wish to thank Richard Yang for valuable advice
regarding these ideas, David Eisenstat for the parity
construction and other discussions, and the anonymous reviewers
for their thoughtful comments and suggestions.
10.



--R

Urn automata.
The Chemical Abstract Machine.
On communicating finite-state machines
A simple game for the study of trust in distributed systems.
Decidability and complexity of Petri net problems-an introduction
Decibility issues for Petri nets - a survey
Lightweight sensing and communication protocols for target enumeration and aggregation.

Mobility increases the capacity of ad hoc wireless networks.
systems
Nondeterministic space is closed under complementation.
Directed di
TAG: a Tiny AGgregation service for ad-hoc sensor networks
Bigraphical reactive systems: basic theory.
Computation: Finite and Infinite Machines.
Randomized non-sequential processes
Collaborative signal and information processing: An information directed approach.
--TR
Nondeterministic space is closed under complementation
The chemical abstract machine
On Communicating Finite-State Machines
Directed diffusion
Mobility increases the capacity of ad hoc wireless networks
Randomized Non-sequential Processes
Decidability and Complexity of Petri Net Problems - An Introduction
Lightweight sensing and communication protocols for target enumeration and aggregation
Catalytic P systems, semilinear sets, and vector addition systems

--CTR
David Pritchard , Santosh Vempala, Symmetric network computation, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
Dana Angluin , James Aspnes , David Eisenstat, Stably computable predicates are semilinear, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
intermittent communication;sensor net;stable computation;finite-state agent;diffuse computation;mobile agent