Details

Autor(en) / Beteiligte

• Strothmann, Thim Frederik
• Scheideler, Christian[Akademischer Betreuer]
• Richa, Andréa W[Akademischer Betreuer]
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]

Titel

Self-* Algorithms for distributed systems : programmable matter & overlay networks

Ort / Verlag

Paderborn

Erscheinungsjahr

2017

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: 18.07.2017
• Open Access
• ger: 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.
• eng: 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++