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.
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.
- Sustaining Cooperation in Dependable Systems: a Game
- Xavier Araújo Morgado
- 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
- 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
- In Proceedings of the 2016 ACM Symposium on
Principles of Distributed Computing (PODC), Chicago (IL), USA, July
- 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.