Abstract :
[en] This thesis analyses the fault-tolerant nature of Evolutionary Algorithms (EAs) executed in a distributed environment which is subjected to malicious acts. Such actions are a common problem in Desktop Grids and Volunteer Computing Systems (DGVCS’s) utilising idle resources shared by volunteers. Due to the vast computational and storage capabilities provided at a low cost, many large-scale research projects are carried out using such set-ups. However, this advantage is obtained at the expense of a challenging, error prone, heteroge neous and volatile environment of execution.
In the volunteer-based systems, such as BOINC, the incentives offered to the contributors attract also malicious users, commonly called cheaters. A cheater typically seeks to obtain the rewards with little or no contribution at all. Additionally, this group may also include "crackers" or "black hat hackers" - users motivated by nothing more than a pure satisfaction from violating computer security.
In this study we use and formalise cheating faults - a model for the behaviours described above, which are a subtype of byzantine (arbitrary) faults. They are mainly characterised by the alteration of outputs produced by some or all tasks forming a distributed execution. The approach differs from the arbitrary faults in its implementation, as usually they are introduced intentionally and from within the boundaries of a system.
The innate fault resilience of EAs has been previously observed in the literature. However, this PhD manuscript offers the first, formal analysis of the impact of cheating faults in this area of optimisation techniques. In particular, the following contributions are proposed:
- An in-depth formal analysis of the cheating-tolerance of parallel Evolutionary Algorithms (EAs), including proofs of convergence or non-convergence towards valid solutions in the presence of malicious acts. A step-wise approach is used, focusing firstly on the most simple variant of an EA that is still of theoretical and practical interest, i.e. a (1 + 1) EA. Then the results are extended to regular (population-based) EAs. The analysis shows that the selection mechanism is crucial to achieve convergence of EAs executed in malicious environments.
- The extension of the study to cheating-resilience of spatially-structured Evolutionary Algorithms (EAs) and gossip protocols. More precisely, we analyse Evolvable Agent Model (EvAg) relying on Newscast protocol to define neighbourhoods in the evolution and the communication layers. There, we provide the necessary conditions for convergence of the algorithm in a hostile environment and we show that the evolutionary process may be affected only by tampering with the connectivity between the computing resources. After that, we design an effective connectivity-splitting attack which is able to defeat the protocol using very few naive cheaters. Finally, we provide a set of countermeasures which ultimately lead to a more robust solution.
These results have been published in several international, peer-reviewed venues and well recognized international journals.
By the variety of problems addressed by EAs, this study will hopefully promote their usage in the future developments around distributed computing platforms such as Desktop Grids and Volunteer Computing Systems or Cloud systems where the resources cannot be fully trusted.
