Xavier Araújo Morgado Vilaça


Sustaining Cooperation in Dependable Systems: a Game Theorectical Approach


Tese submetida para provas de Doutoramento em Engenharia Informática e de Computadores, Instituto Superior Técnico, Universidade de Lisboa.

Abstract

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.


Selected Publications

Sustaining Cooperation in Dependable Systems: a Game Theorectical Approach
Xavier Araújo Morgado Vilaça
PhD Thesis. Instituto Superior Técnico, Universidade de Lisboa.
December, 2016.
Available BibTeX, PhD Thesis.
On the Effectiveness of Punishments in a Repeated Epidemic Dissemination Game.
X. Vilaça and L. Rodrigues.
The 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013). Osaka, Japan, November 2013.
On the Range of Equilibria Utilities of a Repeated Epidemic Dissemination Game with a Mediator.
X. Vilaça and L. Rodrigues.
In Proceedings of the 16th International Conference on Distributed Computing and Networking (ICDCN 2015), Goa, India, January 2015.
Rational Consensus.
J. Halpern and X. Vilaça
In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), Chicago (IL), USA, July 2016.
Accountability in Dynamic Networks.
X. Vilaça and L. Rodrigues
In Proceedings of the 18th IEEE International Conference on Distributed Computing and Networking (ICDCN 2017), Hyderabad, India, January 2017.

Luís Rodrigues