Proceedings of the Third IEEE International Conference
on Self-Adaptive and Self-Organizing Systems, San
Francisco, California, September 2009.

Evolution of Probabilistic Consensus in Digital Organisms
David B. Knoester and Philip K. McKinley
Department of Computer Science and Engineering
Michigan State University
East Lansing, Michigan, USA
Email: {dk, mckinley}@cse.msu.edu

Abstract—The complexity of distributed computing systems
and their increasing interaction with the physical world impose
challenging requirements in terms of adaptation, robustness,and resilience to attack. Based on their reliance on heuristics,
algorithms for consensus, where members of a group agree
on a course of action, are particularly sensitive to these
conditions. Given the ability of natural organisms to respondto adversity, many researchers have investigated biologicallyinspired approaches to designing robust distributed systems. In
this paper, we describe a study in the use of digital evolution, atype of artificial life system, to produce a distributed behavior
for reaching consensus. The evolved algorithm employs a novel
mechanism for probabilistically reaching consensus based on
the frequency of messaging. Moreover, this design approachenables us to change parameters based on the specifics of thedesired system, with evolution producing corresponding flavorsof consensus algorithms. Our results demonstrate that artificial
life systems can be used to discover solutions to engineering
problems, and that experiments in artificial life can inspire newstudies in distributed protocol development.
Keywords-distributed algorithm, consensus, evolutionary
computation, digital evolution, self-organization.

I. I NTRODUCTION
There are many examples of organisms in nature thatexhibit cooperative behaviors of varying complexity. Someof these cooperative behaviors include consensus, where
members of a group agree upon a particular course of action.
Consensus behaviors are visible throughout the spectrum oflife, from decision making in humans [1], to leader electionin schools of stickleback fish [2], to quorum sensing inbacteria [3]. Improving our understanding of such behaviors
has the potential to advance not only the biological sciences,
but also to aid in the design of computational systems.
In distributed computing systems, consensus algorithms
are frequently used to ensure consistency between replicatedcomponents in an effort to increase reliability [4] or toprovide the basis for distributed lock management [5].
However, because bounded-time consensus in the presenceof failures has been proven impossible (the so-called FLP
impossibility proof) [6], numerous heuristics for consensus
have been developed [7]. As computing systems continue
to expand their reach into the natural world, for example
through cyber-physical systems, as well as scaling up insize and complexity, designers are faced with a multitudeof additional complications, some of which may no longer
be amenable to traditional algorithms.
Many of the challenges faced by designers of distributed
systems are shared by biological organisms. For example,
node churn, message loss, and network segmentation all havebiological analogues in organism death, sensory ineffectiveness, and environmental dangers, respectively. As such,many recent approaches to designing distributed systems
have focused on biomimetics, where behaviors observedin nature are replicated in silico [8]. A complementary
approach to biomimetics is evolutionary computation, where
instead of mimicking the behaviors found in nature, we
harness the power of evolution and natural selection, theprocesses that produced those behaviors. Compared to traditional approaches for designing distributed algorithms,
evolutionary computation enables researchers to specify thedesired global behaviors of the system directly and withouta priori knowledge of required local behavior. Instead, these
local behaviors evolve in response to selective pressuresderived from the specified objective. Moreover, while still
relatively early in its application to distributed systems,
evolutionary computation enables the designer to search anenormous solution space, often revealing robust and nonintuitive solutions.
In this study, we use digital evolution [9], a form of
evolutionary computation, to evolve digital organisms thatexhibit consensus. In digital evolution, a population of digitalorganisms (self-replicating computer programs) exists in auser-defined computational environment. These organisms
replicate, compete for resources, and are subject to mutationand natural selection. Over thousands of generations, theycan evolve to survive, and even thrive, under extremely
dynamic and adverse conditions. In this study, we employ
AVIDA [10], a digital evolution platform previously used
to study biological evolution. Digital organisms in AVIDA
exist in a spatial environment, communicate with theirneighbors, and execute their “genome,” a list of virtual
CPU instructions. Recently, AVIDA has been applied to anincreasingly diverse set of engineering problems, from theconstruction of communication networks [11] to adaptive
population control [12].
The contributions of this work are as follows: First, wewere able to evolve a genome that exhibits consensus whenplaced within a group comprising multiple copies of itself.
Second, by analyzing this genome, we show that digital
evolution produced a novel form of consensus based on
probabilistic message forwarding. Third, we simulated thisalgorithm to compare it to examples of distributed consensus
from the literature. These results indicate that evolutionary
computation in general, and digital evolution in particular,
offer a promising approach to designing distributed algorithms.
II. R ELATED W ORK
Replication of the critical components of a distributed
computing system is a well-known method to improveoverall system reliability [13]. Consensus algorithms are
frequently used to ensure that state information shared
among these replica remains consistent [4], [7]. In practice, algorithms such as Paxos [14] are used as the basis
for implementations of consensus [15], which in turn can
support higher-level services such as distributed lock management [5]. As distributed systems continue to increasein scale and complexity, new approaches to the design andimplementation of such algorithms are needed, particularly
as the heuristics used for fault-tolerance are overtaken by thecomplexity of the environments in which these systems are
deployed. Indeed, numerous distributed algorithms alreadyintegrate techniques from dynamic systems [16] to mitigate
the effects of these environments.
The consensus problem has been approached from many
fields of research. While the motivation for this paper
stems from consensus in distributed systems, consensus
is studied in fields as diverse as coordination games [17]and cooperative control [18]. Coordinating the behavior of
multiple agents is also a common problem in evolutionary
robotics [19], and artificial life studies have contributed
to our understanding of the evolution of cooperation andcommunication [20].
In this study, we use a model of the consensus problem
based on [7] and [21], called the n-process id consensus
problem, in which a group of processes seek to reachagreement, or consensus, upon a common process id. The
n-process id consensus problem is similar to the alignment problem [22], where the set of possible states is
simply the n process ids. Necessarily, solving the consensus
problem requires cooperation and communication among
the processes, in addition to a strategy for selecting theagreed-upon value. Additional related forms of consensus
will be discussed in Section VII. Given the fundamental
usefulness of consensus in distributed algorithms, as wellas its theoretical impossibility [6], discovering heuristics forachieving consensus in modern distributed systems is ofgreat importance.
Previous studies that have used evolutionary algorithms to
produce cooperative behaviors have tended to focus on either
the evolution of cooperation under fixed communication

properties [23], or the evolution of communication under
fixed cooperation properties [24]. Here, we provide digitalorganisms with a mechanism for communication and selectfor the ultimate (as opposed to proximal) result of cooperation, leaving evolution to discover the specific cooperativeand communication behaviors.
III. D IGITAL E VOLUTION AND AVIDA
Digital evolution [9] is a form of evolutionary computation originally developed to study evolution in biology.
AVIDA [10], a platform for digital evolution, has also
recently been applied to engineering problems, including theconstruction of communication networks [11] and adaptive
population control for energy efficiency [12]. Although
AVIDA has many characteristics that make it suitable forstudying evolution in biology, here we use AVIDA similarly
to a linear genetic program [25].
There are a number of features that make AVIDA an
appropriate choice for evolving distributed algorithms, andthese features have already made it possible for us to
study various types of cooperative behaviors. First, digitalorganisms in AVIDA have only rudimentary computation
capabilities, comparable to resource-constrained nodes in asensor network. Second, though organisms in AVIDA live
in a digital world that enables them to communicate witheach other, any communication behaviors must evolve within
an environment exhibiting various communication hazards.
Third, AVIDA includes features that enable the evolution ofgroup behaviors. In the remainder of this section, we briefly
describe the structure of a digital organism in AVIDA andthe mechanism by which group behaviors can be evolved.
A. Digital Organisms
Figure 1 depicts an AVIDA population and the structureof an individual organism. Each digital organism comprises
a circular list of instructions (its genome) and a virtual
CPU, and exists in a common virtual environment. Within
this environment, organisms execute the instructions in theirgenomes, and the particular instructions that are executed
determine the organism’s behavior (its phenotype). Instructions within an organism’s genome are similar in appearance
to a traditional assembly language. Instructions enable anorganism to perform simple mathematical operations, control
execution flow, communicate with neighboring organisms,
and replicate. The virtual CPU architecture used in this study
contains a circular list of three general-purpose registers{AX, BX, CX} and two general-purpose stacks {GS, LS}.
As shown in Figure 1, each organism in AVIDA lives in acell located in a fixed location within a spatial environment.
Each cell can contain at most one organism; organisms
cannot live outside of cells. The topology of the environment
defines the neighborhood of each cell, and is user-defined.
For example, the environment topology may be configured
as a grid, a torus, or as a well-mixed environment, whereinc
get-idhallochdiv
rtrvm
rotaterrotater

Registers
Stacks
GS
AX BX
CPU
LS
CX
sendmsg
Heads
rtrvm
rotatelCell
if-less
Instr
Flow
h-div
Interface
getid
Write
Read
getid

Individual selection,
single population

Group selection,
demes

inc

“Multicellularity,”
demes

Figure 2. Levels of selection available within Avida; different shades
represent different genomes.

Figure 1. An Avida population containing multiple genomes (bottom),and the structure of an individual organism (top).

all cells are neighbors of each other (also referred to as aclique). Furthermore, each organism in the environment has
a facing that defines its orientation. This facing may be used
in a number of different ways. For example, an organism
can send a message in the faced direction. The organism
can also sense and manipulate its facing via the get-facing
and rotate-∗ instructions, respectively.
B. Levels of Selection
Figure 2 depicts the three different levels of selection
available within AVIDA. Under the first, individual selection,organisms compete with each other for space (cells) in theirenvironment and are responsible for their own replication,that is, organisms must execute instructions to self-replicate.
In the second level, group selection, the population of digitalorganisms is divided into distinct subpopulations, called
demes. Within each deme, organisms replicate, mutate, andcompete with each other for space and resources. At thesame time, demes also compete with each other for spaceand resources based on the behavior of their constituent organisms. The third level of selection available within AVIDA
is most similar to multicellularity in biology. Here, thepopulation is again split into demes, however, the organisms
within each deme are homogeneous. In this case, a genome
is attached to each deme, rather than individual organisms,
and all organisms within the deme are instantiations ofthat same genome. When a deme replicates, any mutations
occur to the deme’s genome, which is called a digital
germline [11].
For this study, we used CompeteDemes, a framework
within AVIDA that enables the periodic replication andcompetition of demes, in combination with a digital germline
to ensure homogeneity within demes. During the executionof an AVIDA trial, the CompeteDemes framework period-

ically calculates the fitness of each deme via a user-defined
fitness function. This fitness function takes as input a single
deme and produces the fitness of that deme (a floating-point
number) as output. Using the resulting array of fitness values, the CompeteDemes framework then performs fitnessproportional selection, preferentially replicating those demeswith higher fitness, and replacing those demes with lower
fitness. For this study, we define fitness functions basedon the degree to which organisms within a deme achieveconsensus. Over time, the CompeteDemes framework will
preferentially replicate those demes that are more capableof reaching consensus than others, resulting in a populationthat evolves increasingly better solutions. At the end of an
AVIDA trial, the dominant, or most prolific, genome can be
identified for further analysis of its behavior.
IV. M ETHODS
Typically, the AVIDA user will configure the environment
in which the digital organisms live and define the selective
pressures that act upon the population. Once configured,multiple AVIDA trials are conducted to account for thestochastic nature of evolution; although a single result may
be sufficient when searching for an effective algorithm,
multiple trials improve statistical accuracy. In the remainderof this section, we describe the configurations and extensions
to AVIDA that were required for this study of the evolutionof consensus.
Instructions: All relevant instructions employed in thisstudy are summarized in Table I. Of particular note are
the instructions associated with messaging, “opinions,” andthe “flash” capability. These instructions enable organisms
to send and retrieve messages; manipulate their opinion
register, used as the basis for the fitness functions that will bepresented in Section V; and to both sense and trigger virtual
flashes, a synchronization primitive based on the behavior of
fireflies, respectively.
Configuration: We configured AVIDA to use theCompeteDemes process, outlined in Section III-B, withspecific configuration values summarized in Table II. We

Table I
R ELEVANT INSTRUCTIONS FOR THIS STUDY. A LL INSTRUCTIONS ARE
EQUALLY LIKELY TO BE SELECTED AS TARGETS FOR MUTATION .
Instruction
send-msg

retrieve-msg
rotate-left-one
rotate-right-one
get-opinion
set-opinion
bcast1collect-cell-data
get-neighborhood
if-neighborhood-changed

flash
if-recvd-flash

flash-info

Description
Sends a message to the neighbor currently faced by the caller; message
contains contents of BX and CX registers.
Loads the caller’s BX and CX registers from a previously received message.
Rotates the caller counter-clockwise
one step.
Rotates the caller clockwise one step.
Sets register BX to the value of thecaller’s opinion register.
Sets the caller’s opinion register to thevalue in register BX.
Sends a two-word message containing
the values of registers BX and CX
to all immediately neighboring organisms.
Sets register BX to the value of thecell data where the caller lives.
Load a hidden register with a list of theIDs of all neighboring organisms.
Execute the subsequent instruction if
the caller’s current neighbor is different from that when get-neighborhood
was last called.
Broadcasts a “flash” message tocaller’s neighbors, with a configurable
loss rate.
If the caller has received a flash fromany of its neighbors, then execute thesubsequent instruction. Otherwise, skip
the subsequent instruction.
If the caller has ever received a flash,then set BX to 1 and CX to thenumber of cycles since that flash wasreceived. Otherwise, set BX and CX
to 0.

used 400 demes, each comprising 25 digital organisms
connected in a torus topology. Each deme was configured touse a germline to provide homogeneity within demes. Eachtime a deme replicated, the offspring deme was filled with25 copies of the latest (possibly mutated) genome from thatdeme’s germline.
Table II
C OMMON AVIDA CONFIGURATIONS USED FOR THE EXPERIMENTS
DESCRIBED IN THIS STUDY.
Configuration
Trials per experimentMax. population size
Number of demes
Environment topology
Copy mutation rate
Insertion mutation rate
Deletion mutation rate
Time slice
CompeteDemes

Value
30
10,000400, each 5 × 5
Torus
0.0075 (per instruction)
0.05 (per replication)
0.05 (per replication)
5 instructions per update
Compete all demes every 800 updates

V. R ESULTS
A. Simple Consensus
Our initial experiment in the evolution of consensus
focused on the Simple Consensus Dilemma (SCD), based on
the n-process id consensus problem. Informally, we define
the SCD as follows1 :Each agent in a group is assigned a unique identifier. Agents within this group are independent,
and can communicate by sending messages. Eachagent can also designate a value, selected fromthe set of identifiers, as its “opinion.” Following
a period of time during which the agents may
communicate with each other, the opinion of every
agent within the group is examined. If all agents
express the same opinion, the group survives.
If agents express different opinions, the groupperishes. How should the agents act?
The question we are asking then, is: can evolution solve
the SCD, and if so, what strategies will be employed? We
configured each deme as a 5×5 torus of cells, where each ofthese cells was assigned a random 32-bit integer as cell data,
which we used as the identifier for the organism in that cell.
We then defined a fitness function to reward demes whose
constituent organisms set their opinion to a common celldata. The specific fitness function used here was:F = (1 + Smax )2(1)

where F is the resulting fitness value and Smax is the
maximum support, or the number of organisms that haveexpressed the most common opinion. We emphasize that
although organisms are able to set their opinion to any
integer value, only opinions that are set to cell data present
within the deme contribute to the deme’s fitness.
Figure 3 plots the average and best-case performance ofindividual demes across all 30 trials. In this figure, the yaxis represents the fraction of consensus achieved, where avalue of 1 is complete consensus, and the x-axis is in units
of updates, the standard unit of time in AVIDA; an update
corresponds to each organism receiving, on average, five virtual CPU cycles. Here we see that the best-performing demes
achieve consensus after approximately 25,000 updates, while
the average deme steadily approaches consensus.
At the end of 30 trials, six of the dominant (most prolific)
genomes appeared to employ a strategy that searched forthe maximum cell data, while an additional five genomes
searched for the minimum cell data. These approaches are
similar to an evolved strategy from an earlier study on the
diffusion of the maximal sensed value [26]. In that study, weused AVIDA tasks, a mechanism to apply selective pressure
1 This presentation of the consensus problem is intentionally patterned
after the classic Prisoner’s Dilemma game. Game theoretic studies havehistorically provided insight into many of the fundamental aspects ofevolution, such as cooperation [23].

reach consensus, sense that the value that was agreed uponis no longer valid, and then recover to reach consensus on adifferent value. ICD may be thought of as non-stationary
optimization, where the group must continually strive toreach consensus in the face of population turnover. To study
the evolution of behaviors that solve the ICD, we modified
the fitness function described in Section V-A. The specificfitness function we used here was:

1

0.6

0.4

0.2

0

0

0.5

1

1.5

grand mean

Figure 3.

2Update2.5

std. error

3

3.5

(2)

5

x 10
grand max.

Deme performance for the Simple Consensus Dilemma.

to individuals, in order to encourage the evolution of a
distributed behavior that searched for the maximum cell data.
Here, however, we employed a fitness function that operated
only at the group level, enabling evolution to discover themost fit strategy without any guidance as to how consensus
should be reached.
Figure 4 depicts a fragment of an evolved genome thatsolves the SCD by searching for the maximum cell data.
At the individual level, this genome causes the organism to
set its opinion to either the value of data contained in its
own cell, or the contents of a received message, whicheveris larger. When a group of organisms all share this genome,
each will eventually set its opinion to the maximum cell data
to which any of the group members have access.
if-less
retrieve-msg
send-msg
nop-C
nop-C
if-less
nop-C
get-opinion
nop-C
nop-A
..set-opinion.
collect-cell-data

F = (1 + Smax + R · D)2

4

If sensed data is less than the current
opinion, retreive a message.

where F is the resulting fitness, Smax is the maximum
support, R is the number of times the deme has reachedconsensus during this competition period, and D is the sizeof the deme (always 25 in this experiment). To determine
R, each deme in the population is evaluated at every update
to determine if its constituents have reached consensus. If
so, the value of R for that deme is incremented. Wheneverconsensus is reached, the cell data corresponding to theagreed-upon value is reset to a random integer from therange bounded by the maximum and minimum cell data
present within that deme, and the organism in that cellis replaced (killed and overwritten) with a new organism
instantiated from the germline.
Figure 5 plots the average and best-case performance ofindividual demes across all 30 trials. The data show thatthe average deme approaches a single consensus round percompetition period, while the best-case performance of any
deme is two consensus rounds. The remaining experiments
examine various ways in which evolution might discover
improved solutions to the ICD.
7

Send a message containing the current
opinion or last received message.
If the received message is less thanthe current opinion, overwrite themessage with the current opinion.
Set opinion to largest known value.

6
Consensus fraction

Consensus fraction

0.8

5
4
3
2
1

Sense cell data for later use.
00

Figure 4. Genome fragment responsible for searching for the maximum
cell data present within a deme.

0.5

1

1.5

grand mean

Figure 5.

2Update2.5

std. error

3

3.5

4
5

x 10
grand max.

Deme performance for the Iterated Consensus Dilemma.

B. Iterated Consensus
In the next series of experiments, we explored the iterated
consensus dilemma. The Iterated Consensus Dilemma (ICD)
modifies the SCD by introducing rounds, where the groupof agents are repeatedly tasked with reaching consensus.
Whenever a group reaches consensus, the agent with theidentifier that the group has agreed upon is replaced by a
new agent with a different identifier. The particular issue
being examined here is whether a group of organisms can

C. Neighborhood Sensing
In this experiment, we provide additional instructions
that organisms may use to sense their neighborhood forchanges. Specifically, we add the get-neighborhood andif-neighborhood-changed instructions, which enable individuals to sense their environment and determine if theorganisms in their neighborhood are different than the last

7
6
Consensus fraction

time the neighborhood was sensed. This capability could, forexample, be used to sense the replacement of an organism
once consensus had been reached, and thus trigger the
beginning of a new consensus round.
Figure 6 plots average and best-case performance ofindividual demes across all 30 trials. Although the mean
behavior of demes from this experiment is significantly
different from that in Section V-B (p < 0.001, MannWhitney U-test), the best-case performance of any deme
across all trials is unchanged. Based on these results, weconclude that the ability of an individual to sense theirneighborhood does not aid in the evolution of consensus
over organisms without this ability.

5
4
3
2
1
0

0

0.5

1

1.5

grand mean

2
Update

2.5

3

3.5

4
5

x 10

std. error

grand max.

Figure 7. Deme performance on the Iterated Consensus Dilemma, withthe addition of broadcast messaging.

7

5
4
3
2
1
0

0

0.5

1

1.5

grand mean

2
Update2.5

std. error

3

3.5

4
5

x 10
grand max.

Figure 6. Deme performance on the Iterated Consensus Dilemma, withthe addition of neighborhood-sensing instructions.

D. Broadcast
All previous experiments have used relatively simple
mechanisms for sending and receiving messages. Specifically, individuals in the previous experiments have only
been able to send point-to-point messages. Here, we present
a treatment that improved the message-sending capabilityof digital organisms by adding the bcast1 instruction; this
instruction functions identically to send-msg in terms ofregister usage and payload, however, the message is sent
to all neighboring organisms instead of the single faced
organism.
Figure 7 plots average and best-case performance ofindividual demes across all 30 trials. As with the previous
experiment, mean deme performance is significantly different from previous results (p < 0.001), and again, best-caseperformance of individual demes is unchanged. Thus, weconclude that the addition of broadcast messaging alone does
not aid in the evolution of consensus.

Specifically, we established a 0.025% chance per update thata single individual within each deme will be replaced, atwhich point new cell data is assigned as well. At this rate,
on average each deme will experience 20 deaths (out of 25
organisms) during a single competition period.
Figure 8 plots average and best-case performance ofindividual demes across all 30 trials. In this case, not onlyis the mean deme performance significantly different thanprevious results (p < 0.001), the best-case performance of anindividual deme oscillates between three and four complete
consensus rounds, a marked improvement. Based on theseresults, we conclude that a background rate of death hasserved to sensitize evolution to the death of individuals,
thus making it easier for them to sense the start of a newconsensus round.
7
6
Consensus fraction

Consensus fraction

6

5
4
3
2
1
0

0

0.5

1

1.5

grand mean

2
Update2.5

std. error

3

3.5

4
5

x 10
grand max.

Figure 8.
Deme performance and detailed behavior for the Iterated
Consensus Dilemma, with the addition of death during deme competition
periods.

E. Sensing Death
Under the observation that it is the “death” of an individual that signals the start of a new round of consensus, andthat these deaths are rare events, we next examined the effectof a background rate of death on the evolution of consensus.

F. Synchronization
In the final experiment presented here, we added synchronization primitives to the instruction set. Specifically,
we added the flash and get-flash-info instructions, which

Consensus fraction

7

VI. G ENOME A NALYSIS

6

In this section we analyze the most-fit dominant genome
from the experiment described in Section V-F, the same
genome responsible for the behavior in Figure 9(b). Analysis
is complicated by the fact that the evolved behavior depends
on the random cell data and also on interactions with otherindividuals within the deme. Hence, testing an organism inisolation provides little insight into its behavior. To overcome
these difficulties, three different techniques were used. First,
we performed a knockout analysis of each instruction in thisgenome; second, a detailed analysis of the relevant instructions highlighted by the knockout analysis was conducted;
and finally, the putative algorithm was re-implemented andevaluated outside of AVIDA to verify our understanding of
the evolved behavior.

5
4
3
2
1
0

0

0.5

1

1.5

grand mean

2
Update

2.5

3

3.5

4
5

x 10

std. error

grand max.

(a) Average and best-case deme performance.
8

x 10
16
14

A. Knockouts

Opinion

12
10
8
6
4
2
0

0

100

200

mean opinion

300

400
Updateind. opinions

500

600

700

800

consensus reached(b) Representative behavior of a single deme passing multiple consensus rounds.
Figure 9.
Deme performance and detailed behavior for the Iterated
Consensus Dilemma, with the inclusion of synchronization instructions.

send virtual “flashes” (a la fireflies) to an organism’s neighbors, and retrieve information about any sensed flashes,
respectively. We also provide organisms with the bcast1
instruction, enabling them to broadcast messages to all of
their neighbors with a single instruction.
Figure 9(a) plots the average and best-case performanceof individual demes across all 30 trials and Figure 9(b)depicts the specific behavior of a single deme, including
the individual opinions (points), mean group opinion, whenconsensus is reached (vertical line), and the value of thatconsensus (filled circle). Here we see a significant improvement in both the average and best-case deme performance,
where the average deme approaches 1.5 consensus rounds,
and the best-case performance of any deme achieves fiveconsensus rounds. An interesting result brought to light inthis experiment is the role of historical contingency, and its
relationship to instructions. Specifically, it appears as though
a combination of broadcast, sensing, and synchronization
instructions were needed as building blocks for the behavior
shown in Figure 9(b), although the genome responsible,
described below, does not include the flash instruction.

Due to the cryptic nature of evolved genomes, we first
conducted knockout experiments on the genome to identify
the instructions most important to consensus. In AVIDA,a knockout mutation is the replacement of an instruction
in an organism’s genome with a nop-X, an instructionthat performs no computation. By examining the effect ofa knockout mutation on overall group behavior, we canpinpoint those instructions that contribute to consensus.
Specifically, we generated all possible single-point knockouts by replacing each of the instructions in the genome
with a nop-X. There are 86 instructions in this genome,
thus there are 86 possible knockout mutations, and eachof these mutants was tested 30 times, resulting in 2,580
total trials. Figure 10 depicts the resulting fitnesses of thesetrials. For each knockout position, referring to the instructionin the genome that was replaced by a nop-X, a box-plot
for the 30 resulting fitness values was generated. In thisfigure, we see that the majority of fitnesses from a knockout
fall in the range 0.5 × 104 to 1.0 × 104 , indicating thatthose knockouts had very little effect on fitness, and thus
the replaced instructions were not likely to contribute toconsensus. However, knockouts of instructions near position
25, 43, 47, 50-53, and 57 reduced fitness to 0, indicating thatthese instructions are critical for consensus behavior.
B. Annotated genome
Figure 11 depicts the annotated genome. Instructions that
do not affect the overall fitness of this genome are notlabeled. We observe that this genome evolved to use a fairly
short (36 out of 86 instructions) loop to solve the ICD.
Of particular interest are the instructions at position 26
and 61, which together form a loop around the intervening
instructions. Instruction 31 senses cell data, while instructions 33, 35, 44, 48, and 55 retrieve messages that have been
sent to the caller. Instruction 52 sets the organism’s opinion,
while instruction 57 broadcasts its opinion. The importance

4

x 10

Deme fitness

2

1.5

1

0.5

1

5

10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85
Knockout position

Figure 10. Fitness vs. knockout position, averaged over 30 trials. The
most significant instructions are located mid-way through this genome.
1 set-flow
2 nop-C
3 h-search
4 shift-l
5 if-less6 nop-B
7 nop-B
8 swap-stk
9 retrieve-msg
10 flash-info
11 flash-info
12 inc13 nand
14 dec15 retrieve-msg
16 pop17 push18 swap-stk
19 h-search
20 send-msg
21 set-flow
22 get-head
23 nop-C
24 nop-C
25 shift-r
26 h-search
27 inc28 if-less
29 if-cell-data-chan
30 add31 collect-cell-data
32 nop-C
33 retrieve-msg
34 nop-C
35 retrieve-msg
36 nop-C
37 swap-stk
38 nop-C
39 nop-C
40 pop41 if-n-equ
42 rotate-left-one
43 swap-stk
44 retrieve-msg
45 nop-C
46 nop-C
47 push48 retrieve-msg
49 nop-C
50 if-cell-data-chan
51 if-neighborhood52 set-opinion
53 nop-C
54 rotate-right-one
55 retrieve-msg
56 if-less
57 bcast1
58 nop-C
59 nop-C
60 flash-info
61 mov-head
62 if-n-equ
63 nop-C
64 set-opinion
65 shift-r
66 send-msg
67 add68 rotate-right-one
69 add70 add71 get-head72 dec73 sub74 nop-A
75 jmp-head
76 rotate-right-one
77 nop-C
78 nand79 get-head
80 jmp-head
81 flash-info
82 IO
83 nop-C
84 push85 if-n-equ
86 nand

26 h-search
27 inc28 if-less
29 if-cell-data-changed
30 add31 collect-cell-data
32 nop-C
33 retrieve-msg
34 nop-C
35 retrieve-msg
36 nop-C
37 swap-stk
38 nop-C
39 nop-C
40 pop41 if-n-equ
42 rotate-left-one
43 swap-stk
44 retrieve-msg
45 nop-C
46 nop-C
47 push48 retrieve-msg
49 nop-C
50 if-cell-data-changed
51 if-neighborhood-changed
52 set-opinion
53 nop-C
54 rotate-right-one
55 retrieve-msg
56 if-less
57 bcast1
58 nop-C
59 nop-C
60 flash-info
61 mov-head

Beginningof loop.

Retrieve cell
data.
Retrievemessages.

Retrievemessages.
Set opinion
to cell dataor message.
Retrievemessage.
Probabilistic
broadcast
based onretrieved
messages.
Loop.

Figure 11. Annotation of the best-performing final dominant from theexperiment described in Section V-F.

of these instructions for reaching consensus is supported by
the knockout experiments.
C. Evolved Algorithm
Algorithm 1 is pseudocode for the evolved algorithm. The
key component of this algorithm is the timing relationshipbetween the different calls to retrieveMsg() and the ifstatement at line 9. Specifically, these instructions combine to broadcast messages probabilistically and in inverse
proportion to the number of messages that are being sentin the organism’s neighborhood. Through experimentation
both with AVIDA and a simulation of this algorithm written
in Python, we found that consensus was achieved when
the probability of broadcasting a message was below approximately 25%; consensus was rarely achieved at higher
broadcast rates. One implication of this result for distributed
algorithms that warrants further study is the seeming contradiction that sending fewer messages leads to a more stablesystem. Moreover, we observe that this behavior results indecreased synchroneity among organisms, a property thathas been shown to increase system stability [27].
Algorithm 1 Evolved algorithm for solving the ICD.
Require: opinion is null; AX, BX, CX = 0.
loop
2:
CX ⇐ cellData(CX, AX) ⇐ retrieveM sg()
4:
(CX, AX) ⇐ retrieveM sg()
(CX, AX) ⇐ retrieveM sg()
6:
(CX, AX) ⇐ retrieveM sg()
setOpinion(CX)
8:(BX, CX) ⇐ retrieveM sg()
if BX < CX then10:
broadcast(CX, AX)
end if
12: end loop
VII. D ISCUSSION
Based on the analysis of the evolved algorithm fromthe previous section, we can place it in the class of randomized asynchronous consensus protocols [28], where therandom arrival times of messages are exploited to achieveconsensus. The evolved algorithm itself is based on probabilistic messaging, similar to gossip-based protocols suchas that described in [29], and it also bears similarity toa number of algorithms for distributed consensus that use
random processes. For example, Aspnes [30] describes leanconsensus, a probabilistic algorithm for bit-consensus, where
races between processes are exploited to solve consensus;
Aysal et al. [31] describe a probabilistic time-quantization(PTQ) method for producing a distributed average; andChandra [21] presents a solution to n-process id consensus
based on coin-flipping.
In the course of simulating the lean-consensus and PTQ
algorithms for comparison to the evolved strategy, we uncovered a number of important differences. The most significantof these differences is that our model for consensus iscontinuous, and includes the random death of agents. For
example, Figure 12 depicts the representative behavior of

1

Opinion

0.5

0

−0.5

−1

0

10

20

30

mean opinion

40

50
Update60

ind. opinions

70

80

90

consensus reached

Figure 12. Simulation of lean-consensus [30]. All agents are reset once
consensus is reached.

capability of sensing node turnover, as well as instructions
for broadcasting messages and synchronization. We additionally verified that the evolved behaviors scaled to larger
population sizes, and conducted experiments that focusedon the stability of consensus, where we required that allorganisms within a deme maintain a common opinion forconsecutive updates. The details of these additional experiments can be found in [34]. Finally, the addition of message
loss or corruption into the AVIDA system could supply us
with an algorithm for consensus that is resilient to these hazards, just as the inclusion of MANET-specific concerns, forexample, battery conservation, into fitness functions would
enable the simultaneous evolution of distributed behavior
and optimization of resource utilization.
VIII. C ONCLUSION

a simulation of the lean-consensus algorithm. Compared to
Figure 9(b), this behavior appears “cleaner,” with a steadychange in average opinion towards consensus. However,once consensus is reached, this algorithm has no mechanism
to recover from the removal of the agreed-upon value. In
other words, a system based on lean-consensus has nocapacity to “change its mind” once a sufficient number of
agents have agreed upon a course of action. Thus, once
consensus has been achieved, the state of all agents must be
reset in order to subsequently reach consensus. In Figure 12,
we manually restart the algorithm once consensus is reached.
In contrast, the behavior shown in Figure 9(b) contains a
number of oscillations between each consensus, and thedeath of any agent is allowed. A second difference is foundin the communications model. In particular, we assume thatagents are able to communicate only with their neighbors(eight, in this study), as opposed to the multi-writer registermodel used in other studies. This complicates the consensus
problem by requiring that organisms evolve their communication protocol as well as the consensus algorithm. As far
as we are aware, the evolved algorithm presented here is a
novel approach to consensus.
It is possible that some of the techniques designed forthe analysis of traditional probabilistic algorithms could be
used to better understand evolved algorithms. For example,
techniques developed for understanding randomized distributed algorithms in general [32], as well as asynchronous
randomized consensus in particular [33], could improve
our understanding of the evolved algorithm presented here.
Moreover, Olfati-Saber et al. [22] describe a general framework by which consensus algorithms can be studied, thoughsome adaptation for randomized processes would likely berequired.
Broadly speaking, using evolutionary computation to develop distributed algorithms enables the developer to take
into account many of the challenges facing designers ofmodern distributed systems. For example, as part of thisstudy, we examined the effects of granting organisms the

The experiments described in this paper demonstrate that
digital evolution can be used to evolve novel distributed
behaviors for reaching consensus. Based on the results ofdifferent experimental treatments, we can conclude that theavailability of synchronization and broadcast primitives, aswell a low rate of population turnover, have a significant
impact on the evolvability of distributed behavior, even if
those features are not used in the final solutions. Moreover,
we have shown that digital evolution is capable of using features of the environment, in this case, message arrival times,
to produce cooperative behaviors. The results presented inthis paper also demonstrate a near-complete development
life-cycle for using digital evolution as a tool in the design ofdistributed algorithms, including initial evolution, analysis,
and simulation stages.
Ongoing and future work include examining the stabilityof consensus, where instead of holding a common value forat least one update, we require organisms to share the samevalue for a longer period of time; consensus in irregularor self-constructed network topologies; and the introductionof various network and environmental hazards in order todiscover strategies to deal with adverse conditions.
ACKNOWLEDGMENTS
This work was supported in part by NSF Grants CCF0750787, CCF-0820220, and CNS-0751155; U.S. Army
Grant W911NF-08-1-0495; and by a Quality Fund Grant
from Michigan State University.
R EFERENCES[1] C. List, “Democracy in animal groups: a political science
perspective,” Trends in Ecology and Evolution, vol. 19, no. 4,
pp. 168–169, 2004.
[2] D. J. T. Sumpter, J. Krause, R. James, I. D. Couzin, andA. J. W. Ward, “Consensus decision making by fish,” Current
Biology, vol. 18, no. 22, pp. 1773–1777, 2008.

[3] C. M. Waters and B. L. Bassler, “Quorum sensing: Cell-tocell communication in bacteria,” Annual Review of Cell andDevelopmental Biology, vol. 21, no. 1, pp. 319–346, 2005.

[20] K. Wagner, J. A. Reggia, J. Uriagereka, and G. S. Wilkinson,“Progress in the simulation of emergent communication andlanguage,” Adaptive Behavior, vol. 11, no. 1, pp. 37–69, 2003.

[4] M. Barborak, A. Dahbura, and M. Malek, “The consensus
problem in fault-tolerant computing,” ACM Computing Surveys (CSUR), vol. 25, no. 2, pp. 171–220, 1993.

[21] T. D. Chandra, “Polylog randomized wait-free consensus,”
in Proceedings of the ACM Symposium on Principles ofDistributed Computing (PODC), 1996, pp. 166–175.

[5] M. Burrows, “The chubby lock service for loosely-coupled
distributed systems,” in Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, 2006.

[22] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus andcooperation in networked multi-agent systems,” Proceedingsof the IEEE, vol. 95, no. 1, 2007.

[6] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibilityof distributed consensus with one faulty process,” Journal of
the ACM, vol. 32, no. 2, pp. 374–382, 1985.

[23] R. M. Axelrod and W. D. Hamilton, “The evolution ofcooperation,” Science, vol. 211, no. 4489, pp. 1390–1396,
1981.

[7] N. A. Lynch, Distributed Algorithms.
1997.

[24] K. Wagner and J. A. Reggia, “Evolving consensus among
a population of communicators,” Complexity International,
vol. 9, 2002.

Morgan Kaufmann,[8] W. Truszkowski, M. Hinchey, J. Rash, and C. Rouff, “NASA’sswarm missions: The challenge of building autonomous software,” IT Professional, vol. 06, no. 5, pp. 47–52, 2004.
[9] C. Ofria and C. Adami, “Evolution of genetic organization indigital organisms,” in Proceedings of DIMACS Workshop on
Evolution as Computation, 1999.
[10] C. Ofria and C. O. Wilke, “Avida: A software platform forresearch in computational evolutionary biology,” Journal of
Artificial Life, vol. 10, pp. 191–229, 2004.
[11] D. B. Knoester, P. K. McKinley, and C. Ofria, “Cooperative
network construction using digital germlines,” in Proceedingsof the Genetic and Evolutionary Computation Conference(GECCO), 2008.
[12] B. E. Beckmann and P. K. McKinley, “Evolution of adaptive
population control in multi-agent systems,” in Proceedingsof the IEEE International Conference on Self-Adaptive andSelf-Organizing Systems (SASO), 2008, pp. 181–190.
[13] M. C. Pease, R. E. Shostak, and L. Lamport, “Reaching
agreement in the presence of faults,” Journal of the ACM(JACM), vol. 27, no. 2, pp. 228–234, 1980.
[14] L. Lamport, “The part-time parliament,” ACM Transactions
on Computer Systems, vol. 16, no. 2, pp. 133–169, 1998.
[15] T. D. Chandra, R. Griesemer, and J. Redstone, “Paxos madelive: an engineering perspective,” in Proceedings of the ACM
Symposium on Principles of Distributed Computing (PODC),
2007, pp. 398–407.
[16] T. Herman, “Models of self-stabilization and sensor networks,” in Proceedings of the International Workshop on
Distributed Computing (IWDC), 2003, pp. 205–214.
[17] C. F. Camerer, Behavioral game theory: Experiments instrategic interaction. Princeton University Press, 2003.
[18] W. Ren and R. W. Beard, Distributed Consensus in Multivehicle Cooperative Control. Springer, 2007.
[19] G. Baldassarre, D. Parisi, and S. Nolfi, “Distributed coordination of simulated robots based on self-organization,” Artificial
Life, vol. 12, no. 3, pp. 289–311, 2006.

[25] R. Poli, W. B. Langdon, and N. F. McPhee, A Field Guide to
Genetic Programming. Lulu.com, 2008.
[26] D. B. Knoester, P. K. McKinley, B. E. Beckmann, andC. Ofria, “Directed evolution of communication and cooperation in digital organisms,” in Proceedings of the European
Conference on Artificial Life (ECAL), 2007.
[27] A. Campbell and A. S. Wu, “On the significance of synchroneity in emergent systems,” in Proceedings of the International Conference on Autonomous Agents and Multiagent
Systems (AAMAS), 2009.
[28] J. Aspnes, “Randomized protocols for asynchronous consensus,” Distributed Computing, vol. 16, no. 2-3, pp. 165–175,
2003.
[29] M. Jelasity, A. Montresor, and O. Babaoglu, “Gossip-based
aggregation in large dynamic networks,” ACM Trans. Comput.
Syst., vol. 23, no. 3, pp. 219–252, 2005.
[30] J. Aspnes, “Fast deterministic consensus in a noisy environment,” in Proceedings of the ACM Symposium on Principles
of Distributed Computing (PODC), 2000, pp. 299–308.
[31] T. C. Aysal, M. Coates, and M. Rabbat, “Distributed averageconsensus using probabilistic quantization,” in Proceedings ofthe IEEE/SP Workshop on Statistical Signal Processing (SSP),
2007, pp. 640–644.
[32] N. A. Lynch, I. Saias, and R. Segala, “Proving time bounds
for randomized distributed algorithms,” in Proceedings of
the ACM Symposium on Principles of Distributed Computing(PODC), 1994, pp. 314–323.
[33] H. Attiya and K. Censor, “Tight bounds for asynchronous
randomized consensus,” Journal of the ACM (JACM), vol. 55,
no. 5, pp. 1–26, 2008.
[34] D. B. Knoester and P. K. McKinley, “Evolution of probabilistic consensus in digital organisms,” Computer Scienceand Engineering, Michigan State University, East Lansing,Michigan, Tech. Rep. MSU-CSE-09-13, April 2009, http://www.cse.msu.edu/thinktank/consensus-TR.pdf.