Series in
Distributed Computing
edited by Roger Wattenhofer
Vol. 19
Stephan Sebastian Holzer
Distance
Computation, Information Dissemination,
and Wireless Capacity in Networks
1st edition/1. Aufl.
2014, 254 pages/Seiten, € 64,00.
ISBN 978-3-86628-497-5
This dissertation focuses on theoretical
and algorithmic aspects of distributed networks. It studies the power and
limits of wired and wireless networks of devices such as computers, mobile
phones or sensor nodes. While doing so, decreasing levels of abstraction are
considered, and algorithms for basic and complex problems are developed, which
eventually might improve real-world implementations to the best possible.
Computing shortest paths and distances in networks, are problems at the heart of almost every network
application and it is essential to understand their distributed complexity.
This dissertation presents a novel solution (and proves its optimality) for the
problem of computing all pairs shortest paths in the standard model of
distributed computing: Within every round of communication, devices can
exchange a short message with each of their neighbors in the network.
Extensions to a variety of shortest-paths problems as well as computation and
approximation of the diameter, centrality, girth, etc. of a network are
provided. A general framework to prove lower bounds for these types of problems
is established and yields bounds which are often not only best possible, but
the first non-trivial ones. Finally, lower bounds for verification problems are
proven which turned out to yield strong hardness of approximation results for
problems such as minimum spanning tree.
In total, part one of this dissertation
studies the complexity of 25 problems at the heart of networks and reviews
implications for further problems.
In recent years communication became more
and more wireless and the arguably most basic task in these networks is the
coordination of message exchange between devices despite interference. Part two
of this dissertation is devoted to exploring the power and limitations of the
availability of multiple wireless channels when no collision/interference
detection is available. For the problem, where some (unknown) devices need to
send a message to all other devices in the network, a channel-efficient deterministic
algorithm is presented to perform this task as fast as possible. Quality of
this algorithm follows by proving a close lower bound.
To go one step further, part three of this
dissertation considers a model which is used by engineers to model the fading
of a signal's energy with distance and according interference. For a classical
setting, where power used by a transmitter only depends on the distance to the
receiver, an optimal algorithm for capacity/bandwidth maximization in arbitrary
networks is provided. This results marks the end-point
of a sequence of previous studies.
About the author:
Stephan
Holzer received his
B.Sc. degree in 2007 and his Diplom (M.Sc.) in 2008
in mathematics within the excellence program TopMath
from TU Munich, Germany. He spent the academic year 2008/09 as a visiting
fellow at Harvard University working in complexity theory. In 2009 he joined
the Distributed Computing Group headed by Professor Roger Wattenhofer
at ETH Zurich as a Ph.D. student and research assistant. In 2013 he earned his
Ph.D. degree for his work on distributed algorithms and lower bound techniques.
Keywords: Distributed Computing, Wireless Networks, Graph Algorithms,
Approximations, Lower Bounds, All Pairs Shortest Paths, Diameter, Information
Dissemination, Capacity Maximization
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