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.

This dissertation consists of two parts that are dedicated to the study of distributed algorithms for overlay networks and programmable matter. The first part revolves around the topics of robustness against attacks, recovery from faults, and monitoring network properties in the context of overlay networks. More specifically, we introduce network protocols that maintain the connectivity of an overlay network under massive adversarial churn or denial-of-service attacks, we present a self-stabilizing algorithm for the construction of metric graphs, and we initiate the study of hybrid networks by investigating the problem of continuously monitoring properties of an externally-controlled network with the help of an overlay network. In the second part we investigate the algorithmic foundations of programmable matter. Programmable matter refers to a substance that can change its shape or other physical properties in a programmable fashion. We envision programmable matter consisting of simple computational devices that are able to self-organize in order to achieve a collective goal without any central control or external intervention. We present efficient algorithms for the fundamental problems of leader election and shape formation for programmable matter.