Self-stabilizing algorithms for overlay networks
Final Report Abstract
Ziel des DFG-Projekts war es, Grundlagenforschung im Bereich selbststabilisierender Overlay Netzwerke zu betreiben. Ein Overlay Netzwerk ist ein virtuelles Netzwerk, das dadurch gebildet wird, dass Computer Kontaktadressen (wie z.B. IP-Adressen) anderer Computer speichern, um mit diesen zu kommunizieren. Wir haben uns dabei auf Overlay Netzwerke konzentriert, die über dem Internet oder anderen Infrastrukturen gebildet werden, welche generell die direkte Kommunikation zwischen zwei beliebigen Computern erlauben. Ein Algorithmus zur Verwaltung eines Overlay Netzwerks ist selbststabilisierend, wenn dieser die gewünschte Struktur des Overlay Netzwerks aus einem beliebigen schwachen Zusammenhang heraus wieder herstellen kann. Wir waren vor allem an lokal selbststabilisierenden Algorithmen interessiert, d.h. Algorithmen, bei denen die Computer lediglich mit ihren direkten Nachbarn im Overlay Netzwerk interagieren müssen, um die gewünschte Topologie zu erhalten. Zu Beginn des Projekts waren kaum Ergebnisse über selbststabilisierende Overlay Netzwerke bekannt. Das hat sich während des Projekts deutlich geändert. In 7 Veröffentlichungen auf teilweise hochrangigen internationalen Konferenzen konnten wir lokal selbststabilisierende Algorithmen für eine Reihe von Tolopologien vorstellen und formal analysieren. Dazu gehören die sortierte Liste, Skip Listen, Skip Graphen, Delaunay Graphen, das Chord Netzwerk und de Bruijn Graphen. Neben der Entwicklung geeigneter Modelle, Netzwerkmodifikationen und Verfahren mussten auch neue Techniken zur formalen Beweiseführung entwickelt werden. Dazu gehörten z.B. die Einführung geeigneter Brückenkanten, die Verwendung virtueller Knoten und der Einsatz geeigneter Probing Strategien. Der hohe Anspruch der Techniken spiegelt sich darin wieder, dass drei der Veröffentlichungen für die Special Issue der jeweiligen Konferenz eingeladen worden sind, was üblicherweise nur einer Handvoll der besten Veröffentlichungen auf einer Konferenz angeboten wird. Unsere Forschungsergebnisse haben bereits verschiedene neue Forschungsrichtungen initiiert wie die Entwicklung verteilter selbstorganisierender Datenstrukturen (innerhalb des DFG SFB ``Onthe-Fly Computing´´) und erste Forschungen im Bereich selbststabilisierender Partikelsysteme.
Publications
- Tiara: A self-stabilizing deterministic skip list. In: Proc. of the 10th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS), pp. 124-140, 2008
T. Clouser, M. Nesterenko and C. Scheideler
- A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In: Proc. of the 28th ACM Symp. on Principles of Distributed Computing (PODC), pp. 131-140, 2009
R. Jacob, A. Richa, C. Scheideler, S. Schmid and H. Täubig
- A self-stabilizing local Delaunay graph construction. In: Proc. of the 20th Intl. Symp. on Algorithms and Computation (ISAAC), 2009
R. Jacob, S. Ritscher, C. Scheideler and S. Schmid
- Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization. In: Proc. of the 9th Latin American Symposium on Theoretical Informatics (LATIN), pp. 294-305, 2010
D. Gall, R. Jacob, A. W. Richa, C. Scheideler, S. Schmid, H. Täubig
- Corona: a stabilizing deterministic message-passing skip list. In: Proc. of the 13th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS), pp. 356-370, 2011
R. Nor, M. Nesterenko, and C. Scheideler
- Re-Chord: a self-stabilizing chord overlay network. In: Proc. of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 235-244, 2011
S. Kniesburges, A. Koutsopoulos and C. Scheideler
