Self-* Algorithms for distributed systems Article Swipe
YOU?
·
· 2017
· Open Access
·
· DOI: https://doi.org/10.17619/unipb/1-150
· OA: W2945379294
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.
