Details

Autor(en) / Beteiligte

• Feldmann, Michael
• Scheideler, Christian[Akademischer Betreuer]
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]

Titel

Algorithms for distributed data structures and self-stabilizing overlay networks

Ort / Verlag

Paderborn

Erscheinungsjahr

2021

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: 29.03.2021
• Open Access
• ger: Diese Dissertation befasst sich mit der Realisierung von verteilten Datenstrukturen und der Konstruktion von selbststabilisierenden Overlaynetzen. Im ersten Teil dieser Dissertation präsentieren wir verteilte Protokolle für Queues, Stacks und Priority Queues, welche Elemente innerhalb einer logarithmischen Anzahl an Runden einfügen bzw. entfernen können. Zusätzlich respektieren unsere Protokolle neben Semantiken wie sequentielle Konsistenz oder Serialisierbarkeit auch Semantiken welche vom Typ der Datenstruktur abhängen. Wir stellen ebenfalls ein Protokoll vor, welches das Einfügen und Entfernen neuer Knoten realisiert. Ein wichtiges Nebenprodukt stellt ein neues Protokoll dar, welches die verteilte k-Selektion innerhalb einer logarithmischen Anzahl an Runden löst. Der zweite Teil dieser Dissertation befasst sich mit der Konstuktion von Protokollen für selbststabilisierende Overlaynetze, d.h. verteilte Protokolle, welche ein Overlaynetz in endlicher Zeit von einem beliebigen initialen Zustand in einen legitimen Zustand transformiert. Wir präsentieren Protokolle für selbststabilisierende generalisierte De Bruijn Graphen, selbststabilisierende Quadtrees und selbststabilisierende überwachte Skip-Ringe. Jedes dieser Protokolle ist aufgrund seiner Eigenschaften interessant für spezifische verteilte Anwendungen. Generalisierte De Bruijn Netzwerke erlauben Routing mit einer konstanten Anzahl an Hops und sind daher interessant für Anwendungen bei welchen eine geringe Latenz erforderlich ist. Das Protokoll für Quadtrees erfüllt die monotone Suchbarkeit sowie dessen geometrische Variante und ist daher interessant für Dratlosnetzwerke oder Anwendungen aus dem Bereich der Computational Geometry. Der überwachte Skipring kann zur Konstruktion eines selbststabilisierenden Publish-Subscribe Systems verwendet werden.
• eng: This thesis considers the realization of distributed data structures and the construction of distributed protocols for self-stabilizing overlay networks. In the first part of this thesis, we provide distributed protocols for queues, stacks and priority queues that serve the insertion and deletion of elements within a logarithmic amount of rounds. Our protocols respect semantic constraints such as sequential consistency or serializability and the individual semantic constraints given by the type of the data structure. We furthermore provide a protocol that handles joining and leaving nodes. As an important side product, we present a novel protocol solving the distributed k-selection problem in a logarithmic amount of rounds. The second part of this thesis is devoted to the construction of protocols for self-stabilizing overlay networks, i.e., distributed protocols that transform an overlay network from any initial state into a legitimate state in finite time. We present protocols for self-stabilizing generalized De Bruijn graphs, self-stabilizing quadtrees and self-stabilizing supervised skip rings. Each of those protocols comes with unique properties that makes it interesting for certain distributed applications. Generalized De Bruijn networks provide routing within a constant amount of hops, thus serving the interest in networks that require a low latency for requests. The protocol for the quadtree guarantees monotonic searchability as well as a geometric variant of monotonic searchability, making it interesting for wireless networks or applications needed in the area of computational geometry. The supervised skip ring can be used to construct a self-stabilizing publish-subscribe system.