Distributed algorithms for overlay networks and programmable matter
Robert Gmyr · Amtliche Mitteilungen (Universitätsbibliothek Paderborn) · 2018
Diese zweiteilige Dissertation widmet sich der Entwicklung und Analyse verteilter Algorithmen für Overlay-Netzwerke und programmierbare Materie. Der erste Teil besteht aus drei Gruppen von Resultaten, welche sich jeweils auf die Themen der Robustheit, der Fehlertoleranz und der Überwachung von Netzwerken konzentrieren: Zunächst stellen wir Netzwerk-Protokolle vor, welche den Zusammenhang eines Netzwerks unter massivem gegnerischen Churn oder Denial-of-Service-Attacken aufrecht erhalten. Anschließend präsentieren wir einen selbststabilisierenden Algorithmus zur Konstruktion metrischer Graphen. Zuletzt führen wir das Konzept hybrider Netzwerke ein und betrachten eine Reihe von Problemen, in denen Eigenschaften eines dynamischen Netzwerks mit Hilfe eines Overlay-Netzwerks überwacht werden sollen. Im zweiten Teil untersuchen wir die algorithmischen Grundlagen programmierbarer Materie. Programmierbare Materie bezeichnet eine Substanz, die ihre Form oder andere physikalische Eigenschaften auf programmierbare Art und Weise verändern kann. Wir betrachten programmierbare Materie, die aus einer Vielzahl gleichartiger einfacher Einheiten besteht. Die Einheiten verfolgen selbstorganisierend ein gemeinsames Ziel. Dabei unterliegen sie keiner zentralen Kontrolle, sondern agieren vollständig verteilt. Wir stellen effiziente Algorithmen für das Leader-Election-Problem und das Shape-Formation-Problem im Kontext programmierbarer Materie vor.