TY  - THES
AB  - 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. ...
AU  - Setzer, Alexander
CY  - Paderborn
DA  - 2020
DO  - 10.17619/UNIPB/1-1026
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 27.08.2020
N1  - Universität Paderborn, Dissertation, 2020
PB  - Veröffentlichungen der Universität
PY  - 2020
SP  - 1 Online-Ressource (viii, 210 Seiten)
T2  - Institut für Informatik
TI  - Local graph transformation primitives for some basic problems in Overlay networks
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-37849
Y2  - 2024-12-02T16:19:41
ER  -