TY  - THES
AB  - 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.
AU  - Feldmann, Michael
CY  - Paderborn
DA  - 2021
DO  - 10.17619/UNIPB/1-1113
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 29.03.2021
N1  - Universität Paderborn, Dissertation, 2021
PB  - Veröffentlichungen der Universität
PY  - 2021
SP  - 1 Online-Ressource (ix, 158 Seiten)
T2  - Institut für Informatik
TI  - Algorithms for distributed data structures and self-stabilizing overlay networks
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-38727
Y2  - 2026-01-14T16:17:29
ER  -