edited by Roger Wattenhofer
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
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:
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.
theory, mechanism design, implementation theory, peer-to-peer, bittorrent, multicore computing, transactional memory,
contention management, steganography
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 / D-78465 Konstanz / Germany
(0) 7533 97227 Telefax: +49 (0) 7533
http://www.hartung-gorre.de eMail: firstname.lastname@example.org