Evolving Distributed Algorithms with Genetic Programming
University of Kassel, Fachbereich 16: Elektrotechnik/Informatik, Distributed Systems Group, Wilhelmshöher Allee 73, 34121 Kassel, Germany, (2009)Abstract
Distributed systems are one of the most vital components of the economy.
The most prominent example is probably the internet, a constituent
element of our knowledge society. During the recent years, the number of
novel network types has steadily increased. Amongst others, sensor
networks, distributed systems composed of tiny computational devices
with scarce resources, have emerged. The further development and
heterogeneous connection of such systems imposes new requirements on the
software development process. Mobile and wireless networks, for
instance, have to organize themselves autonomously and must be able to
react to changes in the environment and to failing nodes alike.
Researching new approaches for the design of distributed algorithms may
lead to methods with which these requirements can be met efficiently. In
this thesis, one such method is developed, tested, and discussed in
respect of its practical utility.\\
Our new design approach for distributed algorithms is based on Genetic
Programming, a member of the family of evolutionary algorithms.
Evolutionary algorithms are metaheuristic optimization methods which
copy principles from natural evolution. They use a population of
solution candidates which they try to refine step by step in order to
attain optimal values for predefined objective functions.\\
The synthesis of an algorithm with our approach starts with an analysis
step in which the wanted global behavior of the distributed system is
specified. From this specification, objective functions are derived
which steer a Genetic Programming process where the solution candidates
are distributed programs. The objective functions rate how close these
programs approximate the goal behavior in multiple randomized network
simulations. The evolutionary process step by step selects the most
promising solution candidates and modifies and combines them with
mutation and crossover operators. This way, a description of the global
behavior of a distributed system is translated automatically to programs
which, if executed locally on the nodes of the system, exhibit this
behavior. \\
In our work, we test six different ways for representing distributed
programs, comprising adaptations and extensions of well-known Genetic
Programming methods (SGP, eSGP, and LGP), one bio-inspired approach
(Fraglets), and two new program representations called Rule-based
Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in
these representations for three well-known example problems in
distributed systems: election algorithms, the distributed mutual
exclusion at a critical section, and the distributed computation of the
greatest common divisor of a set of numbers. \\
Synthesizing distributed programs the evolutionary way does not
necessarily lead to the envisaged results. In a detailed analysis, we
discuss the problematic features which make this form of Genetic
Programming particularly hard. The two Rule-based Genetic Programming
approaches have been developed especially in order to mitigate these
difficulties. In our experiments, at least one of them (eRBGP) turned
out to be a very efficient approach and in most cases, was superior to
the other representations.
