Series in Distributed
Computing
edited
by Roger Wattenhofer
Vol.
3
Locality, Scheduling, and
Selfishness:
Algorithmic Foundations of Highly
Decentralized Networks.
1st edition/1.
Aufl. 2006, 344 pages/Seiten, € 64,00. ISBN 3-86628-104-8
Large-scale
and highly decentralized networks such as the Internet have emerged as arguably
the most complex computer systems. The size of such networks, as well as their
dynamic, socio-economic, and often wireless nature brings about a large variety
of challenging problems. Achieving efficient and provably robust algorithmic
solutions for these problems therefore necessitates the development and
employment of novel techniques and methods. This dissertation studies three
major concepts that stand out as being of particular importance and interest in
this context: locality, wireless communication, and selfishness.
The
first part of the thesis investigates the possibilities and limitations of local
computation in the classic message passing model of distributed computing.
In large-scale networks, no node is typically able to collect or maintain
global information about the network and each node has to base its decision on
local knowledge only. The thesis derives near-tight upper and lower bounds on the
achievable trade-off between the amount of local knowledge and the resulting global
solution for a variety of fundamental network problems. The second and third
parts of the thesis deal with computation and scheduling in wireless networks.
Specifically, new results on the theoretically achievable throughput of wireless
scheduling and MAC layer protocols are derived. The final part of the thesis
analyzes the impact of selfish and potentially malicious behavior on the
efficiency of peer-to-peer and other decentralized computer networks.
About
the author:
Thomas Moscibroda
received his M.Sc. degree in computer science from the Swiss Federal Institute
of Technology (ETH), Zurich, Switzerland in 2004. In the same year he joined
the Distributed Computing Group of Professor Roger Wattenhofer at ETH Zurich as
a Ph.D. student and research assistant. In 2006 he earned his Ph.D. degree for
his work on distributed algorithms and algorithmic foundations of highly
decentralized networks.
Keywords: Locality, Scheduling, Selfishness, Distributed Computing, Wireless Communication,
Ad Hoc and Sensor Networks, Peer-to-Peer
Direkt
bestellen bei / to order directly from: Hartung.Gorre@t-online.de
Series in Distributed Computing in http://www.hartung-gorre.de