-In this paper we present a model of the dynamics of an interesting class of stochastic cellular automata. Such automata are variants of automata used for density classification and they are chosen because they can be effectively used to address consensus problems. After introducing the topic and the basic notation, we study the dynamics of such automata by means of simulations with varying periods and neighborhood structures. We use the results of simulations to extrapolate a stochastic model of the dynamics of such automata that can be used to estimate stabilization time.
In this seminal work dated 1966 [1], John von Neumann first introduced Cellular Automata (CA) as computing systems capable of self-reproduction and self-organization. Informally, we can think of a CA as a system made of a grid of cells each of which performs a (simple) computation. Each cell is connected to a set of neighbors in order to facilitate information exchange across the grid. All cells are equipped with a single rule that drives all their computations: they all compute the same function synchronously and the complex behavior of the system emerges from (i) the synchronous application of the same rule to different data, and (ii) the flow of information across the grid.
The homogeneous behavior that characterizes CA makes them ideal for the simulation of the dynamics of complex physical systems and they find in such an application domain their most common use. CA have also been used in many other applications where fast and parallel computation is required, e.g., low-level, real-time vision. From a theoretical point of view, CA are an interesting model for massively parallel and synchronous computation.
Today we recognize in CA the possibility of modeling complex and decentralized systems that can exhibit interesting adaptation properties, as discussed later in this paper, and we witness a recent renewal of interest in the subject. In particular, we are mainly interested in CA as a conceptual agent-based model that captures essential features of consensus dynamics. We are not interested in CA as an implementation technology, and the results presented in this paper are meant to be used in implementations that adopt industrial-strength agent technology—JADE [2], WADE [3], and AMUSE [4]— to target mobile scenarios (see, e.g., [5]–[8]).
Moreover, we are interested in modeling the emergent behaviors of wireless sensor networks used to support accurate localization of static (see, e.g., [9]–[11]) and moving (see, e.g., [12], [13]) targets to enhance their adaptability to dynamic environments, and to improve their robustness.
Finally, we recognize that the conceptual framework presented in this paper can be effectively used to model agentbased cooperation (see, e.g., [14], [15]), and it can be employed to enhance the dynamism and the flexibility of workforce management systems that deal with large workforces in complex situations (see, e.g., [16]).
This paper is organized as follows. Section II sets the basic notation about CA and self-stabilizing CA. It extends the ordinary notation with the introduction of a stochastic extension of CA that allows adopting stochastic functions to drive CA. Section III presents the simulations that were performed to study the dynamics of a particular class of CA, and that were used to extrapolate a stochastic model that formalizes the dynamics of the studied CA. Finally, Section IV concludes the paper with a short summary of presented results.
II.
In this section we select one of the available formal definitions of CA and we cite some classic results. The selected definition is reasonably the most general available and we opt for such a definition because it does not restrict neither the size nor the neighborhood structure of automata, which is crucial for the simulations described in Section III.
Definition II.1 A Cellular Automaton A is a structure:
A =< S; d; V; f > where S 6= ; is a finite set of state symbols, d 2 N+ is the dimension of the automata, V L is a finite neighborhood structure over the lattice L = Zd, and f : SV ! S is a transition function known as rule. A cell is a point x in the lattice L.
A CA associates a state s 2 S to each cell x 2 L. A global configuration of states c is defined in:
SL = fc j c : L ! Sg:
The neighborhood structure V L, if not empty, is a set of m 2 N+ vectors used to build the local neighborhood of each cell:
Given V , the neighborhood Vx L of each cell x is created by means of the Abelian group of translations T of L into itself, which is defined in the usual way as < L; + > where + : L ! L is the vector sum in L: 8x 2 L
Vx = fx + v j v 2 V g:
The local configuration of states cVx of a cell x 2 L can be defined using the global configuration as: cVx : Vx ! S
v 7! c(x + v): f : SV
! S cV 7! s:
The local configuration of states allows completing the definition of the rule of a CA as:
In other words, for each cell x 2 L, the rule f associates to the given local configuration of states cVx the future state s 2 S of x. This is better captured if we rewrite f as: 8x 2 L
f (cVx ) = f (s1; s2; : : : ; sm) where si 2 S are the states of the cells in the neighborhood of x: si = cVx (vi); vi 2 V .
Given a global state c0, a CA computes the following global states in terms of repeated and synchronous applications of f to all local configurations of states. Each repeated application of f is known as step.
We can finally define the function that a CA globally computes at each step as: 8x 2 L
Gf : SL ! SL
[Gf (c)] (x) = f (cVx ):
Given an initial global configuration of states c0, we can now compute the final global configuration of states after n steps as a repeated composition:
cn = Gfn(c0):
CA as briefly formalized in this section are characterized by the following major features:
Synchrony: computation is performed synchronously at each cell.
Locality: computation is performed locally at each cell and global computation emerges from independent local computations.
Homogeneity: all cells compute according to the same local function.
Lack of memory: cells compute only on the basis of the current states of the cells in their respective neighborhood and no memory of past states is preserved.
An outstanding result of this formalization of CA is that CA are equivalent to Universal Turing Machines [17]. interested in automata defined over finite subsets of L. We introduce the restriction of CA over finite sets of L by means of so called periodic CA, as follows.
Definition II.2 A cellular automaton A is periodic with period l 2 L if and only if for any initial configuration c0 2 SL: 8n 0; 8x 2 L
cn(x + l) = cn(x):
Such a definition is significant because of a classic result that states that a CA is periodic with period l 2 L if and only if its initial configuration c0 is periodic with period l, i.e.: 8x 2 L
c0(x + l) = c0(x):
In our work we are mainly interested in using CA to model complex systems intended to adapt to varying situations and capable of performing well under diverse conditions, especially for tasks that require decentralized coordination. This is the reason why we propose the following new class of CA: Definition II.3 A CA A =< S; d; V; f > is called selfstabilizing if and only if: 8m 8c0 2 SL; 9n 0; 9k 2 S s:t: n; 8x 2 L cm(x) = [Gfm(c0)](x) = k:
Such a definition is very restrictive because it requires self-stabilizing CA to converge to stable global configurations characterized by all cells having the same state, which is a behavior that is known to be difficult to obtain. For example, it is well known that no periodic CA can solve the majority problem for all initial configurations [18]: no periodic CA can converge to stable global configurations that correctly discriminate if the majority of cells in the initial configuration were in state 0 or in state 1.
We need to extend CA is some way to ensure that the definition of self-stabilizing CA have some practical interest. One possibility is to have different rules across the lattice, which is a possibility that we have already explored and that we adopted to use CA for complex classification tasks [19], [20]. In this work we are interested in exploring another possibility: the use of stochastic rules. Such rules have already been used to solve the majority problem with arbitrary precision [21] and we intend to use them to support the development of a theory of self-stabilizing CA.
The introduction of stochastic rules in CA leads to the following definition¿ Definition II.4 A stochastic CA A is a structure: where S 6= ; is a finite set of state symbols, d 2 N+ is the dimension of the automaton, V L is a finite neighborhood structure over the lattice L = Zd, and f : SV ! S is a stochastic transition function known as stochastic rule.
In practical applications of CA we are not interested in automata that span the entire lattice L; rather, we are often The only difference with a traditional CA is that the local computation of a stochastic CA is now based on a stochastic function and the global configuration of the CA evolves as a discrete stochastic process. Such a process is Markovian because the local computation that f performs depends only on current local configurations and no memory of past configurations is used. In the practice of stochastic CA, the stochastic rules are normally expressed as non-stochastic functions that depend on a random variable v.
The definition of stochastic CA allows extending selfstabilizing CA as follows.
Definition II.5 A stochastic CA A =< S; d; V; f > is called self stabilizing if and only if: 8c0 2 SL; 9n 0; 9k 2 S s:t: 8m n P f8x 2 L; cm(x) = [Gfm(c0)](x) = kg = 1:
The stochastic model of the dynamics of a particular class of self-stabilizing CA that we develop in this section is based on extrapolations from simulations. Such simulations are performed under common assumptions: (i) only 1-dimensional CA are considered (d = 1); (ii) only binary CA are considered (S = f0; 1g); and only periodic CA with period l 2 Z+ are considered.
Under these assumptions, CA are defined over the lattice L = Zl, the set of integers modulo l, and the period l is the actual number of cells in considered CA. We do not assume a specific neighborhood structure and therefore the proposed model is not limited to so called (stochastic) elementary CA [21].
In our simulations, we consider different values of the period l: from 100 to 1000 with step 10. We also consider neighborhood structures of different sizes: m = 3, m = 5, m = 7, and m = 9.
In each case, we assume that the neighborhood structure is V = f (m 1)=2; : : : ; (m 1)=2g, so that the neighbors of a cell x 2 Zl are the previous (m 1)=2 cells, the following (m 1)=2 cells, and the cell x itself.
Let us denote as n0;x the number of cells in state 0 in the
neighborhood Vx of a generic cell x, and as n1;x = m n0;x
the number of cells in state 1 in the same neighborhood. We
define the stochastic rule of the class of CA that we study as:
f (sx+v1 ; : : : ; sx+vm ) =
8> 1
<
>: 0
w:p:
w:p:
n1;x
m
n0;x
m
(
The studied rule says that the probability for a cell to be in state 0 (resp. 1) in the next step is directly proportional to the number of cells in state 1 (resp. 0) in its neighborhood in the current step. The rule ensures that when all cells in the neighborhood of a cell x are in state 0 (resp. 1), next state for x will be 0 (resp. 1) with probability 1.
Due to the randomness in the rule defined in (
We consider values of the period l from 100 to 1000, with step 10. For each of these values and for each of the considered values of m, we perform 1000 (independent) simulation runs, each of which is randomly initialized. We derive a quadratic approximation N m(LS) of N by applying the Least Squares (LS) technique to the results of simulations.
Let us start by considering the results for m = 3. The
local stochastic rule defined in (
Number of Cells 100 200 300 700 800 well known CA called Fuks´ density classifier for the specific case of p = 31 (see [22]).
In Figure 1, the values of N (averaged over the 1000 runs) are shown (blue circles) as a function of the period l which varies from 100 to 1000. As intuitively expected, N is an increasing function of the period l, i.e., more iterations are needed (on average) to reach a stable configuration if a greater number of cells is considered. More precisely, Figure 1 shows that the values of N can be accurately approximated as a quadratic function of l, in agreement with [21]. In particular, the LS technique applied to the considered samples leads to the following quadratic approximation
N ' N3(LS)(l) = 0:16l2 1:10l + 99:
In Figure 1, the values of N3(LS)(l) (red line) are shown and it can be noticed that they fit well the measured values of N for all the values of l. If we define the relative error on a sample as: "(l) = jN (l)
N3(LS)(l)j N (l) we obtain that the average relative error (averaged over the considered values of l) is 2:14%.
We now consider a larger neighborhood structure with m = 5. As in the case with m = 3, we perform 1000 simulation runs for values of the period l from 100 to 1000 in order to investigate the average number of steps N needed to reach a stable configuration. Figure 2 shows the values of N (blue circles) as a function of the period l and the quadratic LS approximation N5(LS)(l) (red line), which is:
N5(LS)(l) = 0:04l2 + 4:93l 459:66:
The quadratic approximation is good also in this case, and the average relative error (averaged over the considered values of l) is 4:6%.
Similarly, in Figure 3 the values of N (blue circles) obtained considering the neighborhood with m = 7 are shown. The quadratic approximation N7(LS)(l) given by
N7(LS)(l) = 0:02l2 + 1:94l 96:03 is also shown (red line). Once again, the LS approximation obtained on the values of l is accurate as the average relative error is 2:4%.
Finally, Figure 4 shows the values of N (blue circles) obtained considering the neighborhood of size m = 9 and their quadratic approximation N9(LS)(l) (red line), given by N9(LS)(l) = 0:01l2 + 1:70l 53:94:
Also in this last case the quadratic approximation is good and it leads to an average relative error of 2:84%.
From the presented result, we can conclude that the larger is the neighborhood, the faster is the convergence to a stable global configuration, which is by far not surprising. Moreover, even if in all cases N is an increasing function of l which can be accurately approximated as a quadratic function, a comparison between the obtained results shows that larger neighborhoods have functions that increase slower.
We now focus on the results obtained with l = 100, for all the values of m 2 f3; 5; 7; 9g and we are interested in analyzing the Probability Mass Function (PMF) of the random variable N.
Keeping m fixed, we consider the number of steps N needed to reach a stable global configuration in a simulation run, and we call Nmax the maximum value of N for all runs. We then divide the interval [0; Nmax] into 50 subintervals Ij , j 2 f1; : : : ; 50g. We then count, for each interval Ij , the number of times that N falls into Ij . Finally, counts are normalized to obtain a PMF. The results are shown in Figure 5 for m = 3, Figure 6 for m = 5, Figure 7 for m = 7, and Figure 8 for m = 9. F M P Fig. 5. PMF of the random variable N for l = 100 and m = 3.
In Figure 9 the Cumulative Distribution Function (CDF) of the random variable N is shown, for l = 100 and for the considered values of m. As expected, greater values of the neighborhood size fasten the convergence of the CDF to 1. Fig. 6. PMF of the random variable N for l = 100 and m = 5.
In each case, we can argue that the PMF can be
approximated as a gamma distribution p(t) = at1=2e bt, defined for
t 0, where a and b are constants that need to be properly set
in order to make sure that the integral of p(t) on its domain is
equal to 1 and that the average value is equal to N . These two
conditions lead to the following expressions for the coefficients
a and b:
p(t)dt = 1
tp(t)dt = N :
(
1=2e( )d =
Z +1 0
a b3=2 = bt, the first integral The same change of variable leads to the following formula
CONCLUSIONS
The stochastic model of the dynamics of some selfstabilizing CA introduced in this paper is an important tool both for the theoretical study of the properties of such automata, and for their practical applications to solve consensus problems. The model provides a good approximation of the dynamics of such automata and it also provides a means to estimate the number of steps needed to converge to a stable configuration. This possibility is particularly important for the practical application of studied CA to solve consensus problems in real-world situations where an estimation of the expected stabilization time is always demanded.
S. Monica and G. Ferrari, “Swarm intelligent approaches to autolocalization of nodes in static UWB networks,” Applied Soft Computing, in press.
S. Monica and G. Ferrari, “UWB-based localization in large indoor scenarios: Optimized placement of anchor nodes,” IEEE Transactions on Aerospace and Electronic Systems, in press.