Reference : Cheating-Tolerance of Parallel and Distributed Evolutionary Algorithms in Desktop Gri...
Dissertations and theses : Doctoral thesis
Engineering, computing & technology : Computer science
Cheating-Tolerance of Parallel and Distributed Evolutionary Algorithms in Desktop Grids and Volunteer Computing Systems
Muszynski, Jakub mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
University of Luxembourg, ​Luxembourg, ​​Luxembourg
Docteur en Informatique
Bouvry, Pascal mailto
Nourdin, Ivan mailto
Fernández de Vega, Francisco
Seredyński, Franciszek
Varrette, Sébastien mailto
[en] Fault tolerance ; Evolutionary Algorithms ; Desktop Grid ; Peer-to-Peer ; P2P ; Volunteer Computing ; Cheating faults ; Cheating-tolerance ; Grid Computing ; Gossip protocols ; Overlay networks ; Theoretical analysis
[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.
Researchers ; Professionals ; Students

File(s) associated to this reference

Fulltext file(s):

Open access
thesis-Jakub-Muszynski.pdfAuthor postprint3.13 MBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.