Coping with selfishness in distributed systems

Distributed systems with autonomous and self-interested participants often exhibit deficiencies due to selfishness of its participants. Mechanism design is the discipline that optimizes systems by taking selfish behavior into account. In the first part of this thesis, we study how a mechanism designer can influence games by promising payments to the players. We first investigate the cost of implementing a desirable behavior. Whereas a mechanism designer can decide efficiently whether strategy profiles can be implemented at no cost at all computing an optimal implementation is generally NP-hard. Second, we introduce and analyze the concept of leverage in a game. The leverage captures the benefits that a benevolent or a malicious mechanism designer can achieve within economic reason, i. e., by taking the implementation cost into account. Mechanism designers can often manipulate games and change the social welfare by a larger extent than the amount of money invested. Unfortunately, computing the leverage is generally intractable as well. In the second part of this thesis, we study the incentives exhibited by transactional memory systems. We find that with most current contention managers, transactional memory systems do not incentivize good programming practice, i. e, programmers are encouraged to make transactions coarse rather than fine-grained. We show how Timestamp-like contention managers can be modified so as to feature beneficial incentives. In general, however, priority-based conflict resolution policies are prone to be exploited by selfish programmers. In contrast, a simple manager that resolves conflicts at random is compatible with good-programming incentives. In the third part of this thesis, we investigate the potential of barter across swarms and along cycles of interest to boosting the market liquidity of tit-for-tat based peer-to-peer file sharing systems. By means of simulations, we find that the proposed measures shorten the median download completion time by more than one third. Furthermore, we study the problem of guiding participants of an established system to using an improved system in a smooth transition. As an entailed problem, we discuss how a conspiring peer can safely determine a connected peer’s type, i. e., how can she learn whether the connected peer is a conspirer or a regular peer without giving away her conspiring identity in the latter case. Our solution is a steganographic handshake. Finally, we look at the problem of how a conspirer can broadcast a message secretly to all fellow conspirers in a monitored environment. For several levels of monitoring, we propose distributed and efficient algorithms that transmit hidden information by varying the block request sequence meaningfully.