Titelaufnahme

Diese Arbeit beschäftigt sich mit Fragestellungen zur Komplexität grundlegender Probleme in dynamischen, d. h. zeitlich veränderlichen, Ad-hoc-Netzen. Basierend auf dem Model von Kuhn et al. (Symposium on Theory of Computing 2010) wird das Netz unter die Kontrolle eines adaptiven Gegenspielers gestellt, der versucht, die effiziente Ausführung von verteilten Algorithmen zu verhindern, und lediglich Zusammenhang in jeder Runde gewährleistet. In dieser Arbeit werden drei wesentliche Aspekte betrachtet, die sich in drei Teilen der Arbeit wiederfinden: Im ersten Teil wird der Gegenspieler zusätzlich geometrisch eingeschränkt und das Verbreiten von Informationen als grundlegendes Problem untersucht. Im zweiten Teil wird die Frage nach der Komplexität des Zählproblems (Wie viele Knoten befinden sich im Netz?) untersucht und das Zählproblem in Bezug zu dem Problem der Verbreitung von Informationen in einer gerichteten Variante von dynamischen Netzen gesetzt. Der dritte Teil beschäftigt sich schließlich mit der wiederholten Berechnung von Aggregationsfunktionen (z. B. das Maximum der Eingaben aller Knoten) in stabileren Varianten dynamischer Netze.

This thesis studies the complexity of fundamental problems in dynamic, i.e., time-variant, ad-hoc networks. Based on the model by Kuhn et al. (Symposium on Theory of Computing 2010), the network is controlled by an adaptive adversary that tries to prevent the efficient execution of algorithms and only guarantees connectivity in each round. In this thesis, three main aspects are considered, which can be found in three different parts of the thesis. In the first part, the adversary is restricted geometrically and an information dissemination problem is analyzed. The second part focusses on the counting problem (How many nodes are there in the network?) and establishes a relation to information dissemination problems. Finally, the third part studies the continuous, i.e., the repeated, computation of aggregation functions (e.g., the maximum of all inputs given to all nodes) in more stable variants of dynamic networks.