@phdthesis{W2009DISS,
  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.},
  address = {Wilhelmsh{\"{o}}her Allee 73, 34121 Kassel, Germany},
  affiliation = {Distributed Systems Group, Fachbereich 16: Elektrotechnik/Informatik, University of Kassel, Germany},
  author = {Weise, Thomas},
  institution = {University of Kassel, Fachbereich 16: Elektrotechnik/Informatik},
  interhash = {c04a928c3b7ebe3c23562fce35b5173a},
  intrahash = {7f90e1843a8496992db2d37119c95a12},
  language = {en},
  location = {Distributed Systems Group, Fachbereich 16: Elektrotechnik/Informatik, University of Kassel, Germany},
  publisher = {University of Kassel, Fachbereich 16: Elektrotechnik/Informatik},
  school = {University of Kassel, Fachbereich 16: Elektrotechnik/Informatik, Distributed Systems Group},
  title = {Evolving Distributed Algorithms with Genetic Programming},
  url = {http://kobra.bibliothek.uni-kassel.de/handle/urn:nbn:de:hebis:34-2009051127217},
  year = 2009
}