Zur Seitenansicht
 

Titelaufnahme

Titel
On the complexity of fundamental problems in dynamic ad-hoc networks
AutorAbshoff, Sebastian
PrüferMeyer auf der Heide, Friedhelm In der Gemeinsamen Normdatei der DNB nachschlagen ; Scheideler, Christian In der Gemeinsamen Normdatei der DNB nachschlagen
Erschienen2015
HochschulschriftPaderborn, Univ., Diss., 2015
Anmerkung
Tag der Verteidigung: 27.04.2015
Verteidigung2015-04-27
SpracheEnglisch
DokumenttypDissertation
URNurn:nbn:de:hbz:466:2-16515 Persistent Identifier (URN)
Dateien
On the complexity of fundamental problems in dynamic ad-hoc networks [0.39 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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.

Zusammenfassung (Englisch)

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.