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 / D-78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de