Search

Die Probleme, die in dieser Dissertation behandelt werden, haben ihren Ursprung im Gebiet der verteilten Systeme und insbesondere der Overlay Netzwerke. Genauer gesagt untersuchen wir, wie wir die dynamische Natur der Overlay Netzwerke ”zähmen” können. Wir fragen uns: ”Wie können wir es schaffen, dass Teilnehmer ständig das Netzwerk verlassen und eintreten können, ohne dass der Zusammenhang des Netzwerkes gefahrdet ist.” Eine andere Frage bezüglich der dynamischen Natur der Overlay Netzwerke, die wir uns stellen ist: ”Wie konnen wir garantieren, dass ein Netzwerk, was momentan eine schlechte Struktur hat, in eine erwunschte Struktur übergeht, und zwar möglichst schnell und effizient?” Um diese Frage zu beantworten, untersuchen wir die Eigenschaft der topologischen Selbststabilisierung in Overlay Netzwerken. Ein Netzwerk besitzt diese Eigenschaft, wenn es seine Struktur (oder Topologie) anpassen kann und eine erwünschte Struktur erreichen kann, unabhängig von der initialen Topologie, die das Netzwerk hat. Dies wird durch bestimmte Protokolle realisiert (selbststabilisierende Protokolle), die standig an jeden Teilnehmer des Netzwerkes lokal laufen, was heißt, dass jeder Knoten Wissen nur über seine direkte Nachbarn im Netzwerk verfügt und Aktionen gemäß dieses Wissens durchführt. In dieser Dissertation stellen wir effiziente selbststabilisierende Protokolle fur diverse Topologien vor. Diese Topologien haben gewisse Eigenschaften, die für diverse Anwendungen erwünscht sind. Die Qualitat der Effizienz unser Protokolle messen wir anhand der Anzahl der Bits, die durch das Protokoll gesendet werden, als auch die Zeit, die benötigt wird, um die erwünschte Topologie zu erreichen. The problems studied in this thesis originate from the field of distributed systems and in particular overlay networks. More specifically, we study how to handle the dynamic nature of overlay networks.We ask ourselves the question: ”How can we handle the situation in which participants can constantly join and leave the network, without endangering that the network disconnects?” Another question we ask ourselves regarding the dynamic nature of overlay networks is: ”How can we guarantee that a network which currently has a structure that is in a bad state, recovers to a desired structure quickly and efficiently?” In order to answer that question, we study topological self-stabilization in overlay networks. This is a property that a network has, if it is able to adapt its structure (or topology) and reach a desired topology, independently of the original topology that the network has. This is done by specific protocols (self-stabilizing protocols), which are run constantly on each network participant and are local: i.e., each node has knowledge only about its direct neighbors in the network and takes actions according to that knowledge.In this thesis we present efficient self-stabilizing protocols for several topologies. These topologies have specific properties that are desired for various applications. The quality of the efficiency of our protocols is measured according to communication bits that are sent, due to our protocols, as well as according to the time needed in order for the desired topology to be reached. Andreas Koutsopoulos ; [Reviewers: 1. Prof. Dr. Christian Scheideler (advisor), 2. Prof. Dr. Friedhelm Meyer auf der Heide] Tag der Verteidigung: 16.12.2015 University of Paderborn, Univ., Dissertation, 2015