Series in Distributed
edited by Roger Wattenhofer
Locality, Scheduling, and Selfishness:
Algorithmic Foundations of Highly
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