Zur Seitenansicht
 

Titelaufnahme

Titel
Self-* Algorithms for distributed systems : programmable matter & overlay networks / Thim Frederik Strothmann ; reviewers: Prof. Dr. Christian Scheideler, Paderborn University, Prof. Dr. Andréa W. Richa, Arizona State University, Prof. Dr. Friedhelm Meyer auf der Heide, Paderborn University
AutorStrothmann, Thim Frederik
BeteiligteScheideler, Christian In der Gemeinsamen Normdatei der DNB nachschlagen ; Richa, Andréa W. In der Gemeinsamen Normdatei der DNB nachschlagen ; Meyer auf der Heide, Friedhelm In der Gemeinsamen Normdatei der DNB nachschlagen
ErschienenPaderborn, 2017
Ausgabe
Elektronische Ressource
Umfang1 Online-Ressource (xviii, 193 Seiten) : Illustrationen
HochschulschriftUniversität Paderborn, Dissertation, 2017
Anmerkung
Tag der Verteidigung: 18.07.2017
Verteidigung2017-07-18
SpracheEnglisch
DokumenttypDissertation
URNurn:nbn:de:hbz:466:2-28986 Persistent Identifier (URN)
DOI10.17619/UNIPB/1-150 
Dateien
Self-* Algorithms for distributed systems [1.9 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

In dieser Doktorarbeit werden zwei Szenarien für Self-* Algorithmen in verteilten Systemen betrachtet: selbst-organisierende programmierbare Materie und monotone Suchbarkeit für selbst-stabilisierende Overlaytopologien. Das erste Thema betrachtet programmierbare Materie, welche aus kleinen, in ihren rechnerischen Fähigkeiten beschränkten Einheiten besteht, die Partikel genannt werden. Programmierbare Materie solcher Art kann im amoebot Model betrachtet werden. Es wird eruiert ob programmierbare Materie zwei grundlegende Probleme in diesem Model lösen kann: Coating und Shape Formation. Im Coating sind die Partikel mit einem unbekannten Objekt verbunden und es ist das Ziel dieses gleichmäßig zu ummanteln. Bei der Shape Formation soll die Materie einfache Formen konstruieren, wobei die Größe der Form mit der Anzahl der Partikel skaliert. Dazu ergänzend wird die Fähigkeit von programmierbarer Materie konstanter Größe betrachtet, die zu einem unbekannten Objekt verbunden ist. Das zweite Thema fokussiert sich auf das Problem Suchbarkeit monoton in einer Overlaytopologie aufrecht zu erhalten, während sich diese stabilisiert. Konkret werden selbst-stabilisierende Protokolle für die Linientopologie betrachtet. Zusätzlich zu der Konvergenz sollen die Protokolle auch die Eigenschaft der Suchbarkeit monoton aufrechterhalten. Das Problem wird in zwei Varianten betrachtet: die strikten Linie und die Super-Linie. In der ersten Variante ist die Liste über alle Knoten die Zieltopologie. In der zweiten Variante werden mehrere Nachbarn in der Zieltopologie erlaubt, aber die Linie muss ein Subgraph sein. Für beide Szenarien wird: (i) ein selbst-stabilisierendes Protokoll präsentiert, (ii) ein Routing Protokoll für Suchnachrichten angegeben, (iii) die Selbst-Stabilisierung bewiesen und (iv) der Erhalt der monotonen Suchbarkeit bewiesen.

Zusammenfassung (Englisch)

This thesis considers two scenarios for self-* algorithms in distributed computing: self-organizing programmable matter and monotonic searchability for self-stabilizing overlay topologies. The former topic considers programmable matter that consists of tiny computationally limited units called particles, which can move in two-dimensional space, bond and communicate with each other. This kind of matter is studied in the recently introduced amoebot model and we investigate the feasibility of solving fundamental problems for programmable matter in that model. More precisely, the focus is on two major problems: coating and shape formation.In coating, the particles are connected to an unknown object and the ultimate goal is to coat the object as evenly as possible. In shape formation, we focus on building basic shapes out of programmable matter where the size of the constructed shape scales with the number of particles. Supplementary to these two central problems we investigate the ability of constant-size programmable matter that is connected to an unknown object. The latter topic focuses on the problem of maintaining searchability in an overlay topology while that topology is stabilizing. More specifically, we investigate self-stabilizing protocols for the line topology. In addition to the convergence process, the protocols should also monotonically maintain a property called searchability. We study this problem in two variants: the strict line topology and the super-line topology. In the first variant the ultimate goal topology is a line over all nodes. In the second variant, we allow the goal topology to have more edges, but the line has to be a subgraph of it. In both scenarios we present: (i) a protocol that stabilizes to the desired protocol, (ii) a routing protocol that is able to route search messages, (iii) a self-stabilization proof and (iv) a monotonic searc++