Details

Autor(en) / Beteiligte

• Setzer, Alexander
• Scheideler, Christian[Akademischer Betreuer]
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]

Titel

Local graph transformation primitives for some basic problems in Overlay networks

Ort / Verlag

Paderborn

Erscheinungsjahr

2020

Link zum Volltext

• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)
• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)

Link zu anderen Inhalten

• Volltext
• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 27.08.2020
• Open Access
• ger: Diese Dissertation betrachtet einige grundlegende Overlay-Netz-Probleme. Sie konzentriert sich dabei auf die besondere Rolle, welche Primitive zur Transformation des Netzwerkgraphen in ihrer Lösung spielen. Im ersten Teil untersuchen wir die Komplexität der Berechnung einer kürzesten Abfolge von Anwendungen von Graphtransformationsprimitiven, um einen Graphen in einen anderen umzuformen. Hierfür betrachten wir zwei Mengen von Primitiven (eine für ungerichtete und eine für gerichtete Graphen), die sich im Kontext von Overlay-Netzen als nützlich erwiesen haben. Wir zeigen auf, dass dieses Problem zwar \NP-schwer ist, können aber Approximationsalgorithmen mit konstantem Approximationsfaktor für beide Mengen von Primitiven angeben. Im zweiten Teil behandeln wir das Problem der monotonen Suchbarkeit in selbststabilisierenden Overlay-Netzen. Wir entwickeln einen generellen Ansatz, um montone Suchbarkeit zu garantieren, wenn die Zieltopologie ein Obergraph der Linientopologie ist. Außerdem stellen wir ein Protokoll vor, welches das Problem der monotonen Suchbarkeit für die Linientopologie löst und selbst dann korrekt arbeitet, wenn Knoten das System verlassen dürfen. Lokale Graphtransformationsprimitive erweisen sich hierbei als wichtiger Bestandteil unserer Lösungen. Im dritten Teil entwickeln wir das Relay-Modell, ein neues Modell zur Vernetzung von Knoten. Während es im Standard-Modell nicht möglich ist, dass Knoten das System gewissenhaft (das heißt, ohne den Zusammenhang zu gefährden) verlassen, sofern sie nicht Zugang zu einem Orakel haben, werden diese Orakel im Relay-Modell nicht benötigt. Wir zeigen, wie das Relay-Modell selbststabilisierend implementiert werden kann und stellen außerdem einen generellen Ansatz vor, um das Verlassen von Knoten in diesem Modell zu behandeln. ...
• eng: This thesis considers some basic problems in overlay networks, focusing on the particular role that primitives for the transformation of the network graph play in their solution. In the first part, we investigate the complexity of computing a minimum sequence of applications of graph transformation primitives to transform one graph into another. For this we consider two sets of primitives (one for undirected and one for directed graphs) that have proved to be useful in the context of self-stabilizing overlay networks. We find that the problem is \NP-hard but are able to develop constant-factor approximation algorithms for both primitive sets. In the second part, we study the problem of monotonic searchability in self-stabilizing overlay networks. We develop a general approach to guarantee monotonic searchability when the target topology is a supergraph of the line. Moreover, we present a protocol that solves monotonic searchability for the line topology and works correctly when nodes are allowed to leave the system as well. For our solutions, local graph transformation primitives turn out to serve as an important ingredient. In the third part, we develop the relay model, a new model for interconnecting nodes. Whereas in the standard model nodes were not able to leave the system faithfully (i.e., without harming connectivity) unless they had access to an oracle, in the relay model these oracles are not required. We show how to implement the relay model in a self-stabilizing fashion and provide a generic approach to handle node departures in this model. Moreover, we prove the relay model to be universal. This means that arbitrary graph transformations are possible in this model. ...