TY  - THES
AB  - 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.
AU  - Götte, Thorsten
CY  - Paderborn
DO  - 10.17619/UNIPB/1-2217
DP  - Universität Paderborn
LA  - ger
N1  - Tag der Verteidigung: 25.03.2025
N1  - Universität Paderborn, Dissertation, 2025
PB  - Veröffentlichungen der Universität
PY  - 2025
SP  - 1 Online-Ressource (vii, 302 Seiten) Illustrationen, Diagramme
T2  - Institut für Informatik
TI  - Distributed algorithms for modern communication networks
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-54281
Y2  - 2026-02-05T11:30:16
ER  -