Distributed Algorithms for Modern Communication Networks

In dieser Arbeit betrachten wir algorithmische Lösungen für fundamentale Probleme in modernen Kommunikationsnetzen. Im ersten Teil dieser Arbeit zeigen wir, wie man ein Overlay-Netzwerk mit Grades und Durchmesser O(log n) in O(log n) Runden ausgehend von einem beliebigen, schwach verbundenen Graphen konstruiert. Wir gehen von einem synchronen Kommunikationsnetz aus, in dem Knoten Nachrichten an alle Knoten senden können, deren Adresse sie kennen, und neue Verbindungen durch das Versenden dieser Adressen hergestellt werden können. Wenn der Ausgangsgraph des Netzwerks schwach zusammenhängend ist und einen konstanten Grad hat, dann konstruiert unser Algorithmus die gewünschte Topologie mit hoher Wahrscheinlichkeit in O(log n) Runden, wobei in jeder Runde nur O(log n) Nachrichten sendet und empfängt. Da das Problem nicht schneller gelöst werden kann als durch sogenanntes Pointer Doubling für O(log n) Runden (was sogar erfordern würde, dass jeder Knoten Ω(n) Bits kommuniziert), ist unser Algorithmus asymptotisch optimal. Außerdem zeigen wir, wie unser Algorithmus zur effizienten Lösung von Graphenproblemen im HYBRID modelverwendet werden kann. Motiviert durch die Idee, dass Knoten zwei verschiedene Arten der Kommunikation besitzen, nehmen wir an, dass die Kommunikation der Kanten unbeschränkt ist, während nur polylogarithmisch viele Nachrichten über Kanten gesendet werden können, die während der Ausführung eines Algorithmus etabliert wurden. Für einen (ungerichteten) Graphen G mit beliebigem Grad zeigen wir, wie man zusammenhängende Komponenten und einen Spannwald mit hoher Wahrscheinlichkeit in O(log n) Zeitberechnen kann. Außerdem zeigen wir, wie man ein MIS mit hoher Wahrscheinlichkeit in O(log ∆ + log log n), berechnet, wobei ∆ der Grad von G ist. Im zweiten Teil der Arbeit betrachten wir das Problem der Berechnung von kompakten Routing-Tabellen und Dekompositionen mit geringem Durchmesser für einen (gewichteten) Graphen G := (V, E, ℓ), der durch k kürzeste Wege separiert werden kann. Zu dieser Klasse von Graphen gehören planare Graphen, Graphen mit beschränkter Treewidth und Graphen, die einen festen Minor Kr ausschließen. Wir präsentieren Algorithmen im CONGEST- und im neuartigen HYBRID-Kommunikationsmodell, die in allen relevanten Parametern konkurrenzfähig sind:• Für einen gegebenen Parameter ϵ > 0 berechnen wir ein Routing-Schema mit Stretch 1 + ϵ. Unser Schema berechnet Label der Größe Oe(kϵ−2) und wird in Oe(kϵ−3) Zeit im HYBRID-Modell, und Oe(kϵ−3· HD) Zeit in CONGEST. Dabei bezeichnet HD den Hopdurchmesser des Graphen.• Für einem Parameter D > 0 unterteilt unser Algorithmus zur Dekomposition den Graphen in zusammenhängende Subgraphen mit starkem Durchmesser D. Eine Kante e ∈ E der Länge ℓe hat ihre Endpunkte in zwei verschieden Subgraphen mit der Wahrscheinlichkeit O(ℓe·log(k log n)/D). Die Dekomposition kann in Oe(k) Zeit im HYBRID-Modell und O˜(kHD) Zeit in CONGEST berechnet werden. Wir stellen verteilte und parallele Implementierungen von sequenziellen Divide-and-Conquer-Algorithmen vor, bei denen wir exakte kürzeste Pfade durch approximative kürzeste Pfade ersetzen. Im Gegensatz zu exakten Pfaden können diese in der verteilten und parallelen Umgebung effizient berechnet werden. Außerdem, zeigen wir, dass es ausreicht, anstelle der expliziten Berechnung von Vertex-Separatoren, einige zufällige Pfade begrenzter Länge zu wählen und die Separatoren um diese herum zu konstruieren. Schließlich stellen wir einen SetCover-Algorithmus für das Beeping-Modell vor. Unser Algorithmus läuft in O(k3) Zeit und hat eine erwartete Approximationsgüte von O(∆3/k log2 ∆). Der Wert k ∈ [3, log ∆] ist ein Parameter, mit dem wir Laufzeit gegen Approximationsgüte eintauschen können, ähnlich wie bei dem Algorithmus von Kuhn und Wattenhofer [PODC ’03]. Dieser Algorithmus kann erweitert werden, um das DominatingSet-Problem in der D-Nachbarschaft eines Graphen mittles eines verteiltes Algorithmus effizient zu lösen.

---

This thesis considers algorithmic solutions to problems that arise in the theoretical study of modern communication networks, such ast he Internet. The thesis is divided into two main parts. In the first part of this thesis, we show how to construct an overlay network of degree O(log n) and diameter O(log n) in O(log n) time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. If the initial network’s graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in time O(log n), w.h.p. Since the problem cannot be solved faster than by using pointer jumping for O(log n) rounds (which would even require each node to communicate Ω(n) bits), our algorithm is asymptotically optimal. Additionally, we show how our algorithm can be used to efficiently solvegraph problems in the novel HYBRID model. Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted, whereas only polylogarithmically many messages can be sent over edges that have been established throughout an algorithm’s execution. For an (undirected) graph G with arbitrary degree, we show how tocompute connected components and a spanning forest in O(log n) time, w.h.p. Furthermore, we show how to compute an MIS in timeO(log ∆ + log log n), w.h.p., where ∆ is the initial degree of G. In the second part of the thesis, we consider the problems of computing compact routing tables and low-diameter decompositions for a (weighted) graph G := (V, E, ℓ) that can be separated through k shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor Kr. We present algorithms in the CONGEST and the novel HYBRID communication model that are competitive in all relevant parameters:• For a given parameter ϵ > 0, we compute a routing scheme with stretch 1 + ϵ. Our scheme computes labels of size Oe(kϵ−2)and is computed in Oe(kϵ−3) time in the HYBRID model and Oe(kϵ−3· HD) time in CONGEST. Here, HD denotes thenetwork’s hop diameter.• Given a parameter D > 0, our low-diameter decomposition algorithm divides the graph into connected subgraphs of strongdiameter D. An edge e ∈ E of length ℓe has endpoints in different subgraphs with probability O(ℓe·log(k log n)/D). The decomposition can be computed in Oe(k) time in the HYBRID model and O˜(kHD) time in CONGEST.Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replaceexact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficientparallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Finally, we present a SetCover algorithm in the Beeping model. Our algorithm runs in O(k3) time and has an expected approximation ratio ofO(∆3/k log2 ∆). The value k ∈ [3, log ∆] is a parameter that lets us trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [PODC ’03]. This algorithm can then be extended to effieciently solve the DominatingSet-problem in a graph’s D-neigborhood in a distributed fashion.