David B. Knoester and Philip K. McKinley
April, 2009
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 respond to adversity, many researchers have investigated biologically-inspired approaches to designing robust distributed systems. Examples include biomimetics, which mimic behaviors such as swarming found in nature, as well as evolutionary computation methods, such as genetic algorithms and neuroevolution, which simulate the natural processes that produce those behaviors. A related but fundamentally different technique is digital evolution, a type of artificial life system whereby a population of self-replicating computer programs exists in a user-defined computational environment and is subject to instruction-level mutations and natural selection. Over thousands of generations, these digital organisms can evolve to survive, and thrive, under extremely dynamic and adverse conditions. In this paper, we describe a study in the use of digital evolution 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 approach enables us to change parameters based on the specifics of the desired system, with evolution producing corresponding flavors of 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 new studies in distributed protocol development.
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format.