Distance computation, information dissemination, and wireless capacity in networks

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.