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:
Series in Distributed Computing in

Direkt bestellen bei / to order directly from:

Hartung-Gorre Verlag

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228 eMail: