Series in Distributed Computing
edited by Roger Wattenhofer
Vol. 17

 

Raphael Eidenbenz

Coping with Selfishness in Distributed Systems:

Mechanism Design in Multi-Core and Peer-to-Peer Systems

 

1st edition/1. Aufl. 2012, 186 pages/Seiten, € 64,00.
ISBN 3-86628-419-5 and 978-3-86628-419-7

 

 

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.

About the author:

 

Raphael Eidenbenz received his M.Sc. degree in computer science from ETH Zurich, Switzerland, in 2007. In 2008, he joined the Distributed Computing Group of Professor Roger Wattenhofer at ETH Zurich as a Ph.D. student and research assistant. In 2012, he earned his Ph.D. degree for his work on mechanism design in distributed systems.

 

Keywords: game theory, mechanism design, implementation theory, peer-to-peer, bittorrent, multicore computing, transactional memory, contention management, steganography


 

Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de
Series in Distributed Computing in http://www.hartung-gorre.de

Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de

Hartung-Gorre Verlag

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227  Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de   eMail: verlag@hartung-gorre.de