Thesis presented: Xavier Araújo Morgado Vilaça

Congratulations to Xavier Araújo Morgado Vilaça for successfully defending his PhD thesis:

Sustaining Cooperation in Dependable Systems: a Game Theorectical Approach

A dependable distributed system is composed of different processes that execute a distributed protocol to provide some reliable distributed service. Typically, one assumes that all processes cooperate by executing the specified protocol, unless faults occur; if the processes do not cooperate, then the service that the system is intended to provide may be compromised. Unfortunately, the assumption that processes do not deviate from the protocol may not hold in open systems, where each process is under the control of a different entity. In fact, if the entities are selfish and they benefit from deviations, then they may change the protocol run by the processes. To avoid this problem, protocols must sustain cooperation, i.e., they must provide incentives that deny any benefits to the entities responsible for deviations.
One way of modelling selfish behaviour is to adopt the approach of Game Theory. In this approach, processes are seen as being under the control of rational agents that seek to maximize individual utility functions, interactions are modelled as games, and protocols correspond to strategies of the game that specify the actions taken at each point in time. The main goal is to devise equilibria protocols, i.e., protocols such that no agent increases its utility by causing a deviation. Equilibria protocols sustain cooperation, thus being extremely relevant to the development of dependable distributed systems.

In this work, we apply Game Theory to identify and analyse protocols that sustain cooperation in three fundamental distributed problems: (i) the problem gossip dissemination, (ii) the problem of pairwise exchanges of messages over links of a dynamic network, and (i) the problem of consensus with crash failures. Our main results identify necessary and sufficient conditions for devising equilibria protocols that solve the aforementioned problems. These results unveil the necessary and sufficient requirements for the construction of dependable distributed systems robust to selfish behaviour.