Games on dynamic networks : routing and connectivity

Radmacher, Frank G.; Thomas, Wolfgang

doi:4436

Games on dynamic networks : routing and connectivity = Spiele auf dynamischen Netzen : Routing und Konnektivität

Radmacher, Frank G. (Author)

2012 & 2013

VerantwortlichkeitsangabeFrank G. Radmacher

ImpressumMünster : MV-Verl. 2012

Umfang199 S. : graph. Darst.

ISBN978-3-86991-775-7

ReiheMV-Wissenschaft

Zugl.: Aachen, Techn. Hochsch., Diss., 2012

Druckausgabe: 2012. - Onlineausgabe: 2013. - Zsfassung in dt. u. engl. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Thomas, Wolfgang (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2012-02-24

Online
URN: urn:nbn:de:hbz:82-opus-44365
URL: https://publications.rwth-aachen.de/record/210414/files/4436.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Theoretische Informatik (Genormte SW) ; Spieltheorie (Genormte SW) ; Informatik (frei) ; dynamische Netze (frei) ; theoretical computer sciences (frei) ; game theory (frei) ; dynamic networks (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
msc: 91A80 * 91A43 * 91A05

Kurzfassung
Unendliche Spiele sind ein mächtiges Modell für die Analyse dynamische Netzwerke, die fortwährend topologischen Veränderungen ausgesetzt sind. In diesem Rahmen vertreten die Spieler die sich entgegenwirkenden Kräfte im Netzwerk. Diese Dissertation behandelt drei verschiedene Zweipersonenspiele, welche sich insbesondere auf das Garantieren von Konnektivitäts- und Routing-Eigenschaften richten. In jedem Modell muss ein Spieler die Funktionstüchtigkeit des Netzwerkes herstellen, während der Gegner Ausfälle und Lasten erzeugt, die während des Betriebs auftreten. Im ersten Teil betrachten wir Sabotage-Spiele, die van Benthem 2002 einführte. In diesen Spielen durchquert ein Runner einen Graphen und versucht einen Zielknoten zu erreichen, während ein Blocker Kanten entfernt. Wir verfeinern dieses Spiel auf zwei Arten: Zum einen betrachten wir eine allgemeinere Gewinnbedingung, die in linearer temporaler Logik angegeben wird. Zum anderen untersuchen wir die Variante, in der Blocker durch einen probabilistischen Spieler ersetzt wird. Wir zeigen, dass in beiden Fällen das Entscheidungsproblem, ob Runner gewinnt, PSPACE-vollständig bleibt. Im zweiten Teil entwickeln wir ein Routing-Spiel, in dem ein Routing-Spieler Pakete an ihre Zielknoten ausliefern muss, während ein Lasten-Spieler ununterbrochen Pakete erzeugt und Verbindungen im Netzwerk für bestimmte Zeit blockiert. Wir beweisen grundlegende Grenzen für das Berechnen von Routing-Strategien; wir zeigen jedoch auch algorithmische Lösungen auf. Die Ergebnisse hängen sowohl von der gewünschten Routing-Eigenschaft als auch von der Gröbe des Modells ab. Für bestimmte Szenarien entwickeln wir realisierbare Routing-Algorithmen, welche jeweils eine Routing-Eigenschaft gegen jedes mögliche Verhalten des Lasten-Spielers sicherstellen. Im dritten Teil führen wir ein Konnektivitätsspiel ein, in dem ein Constructor gegen einen Destructor antritt. Während Destructor Knoten löscht, kann Constructor Knoten wiederherstellen und unter bestimmten Bedingungen sogar neue Knoten erzeugen. Auch modellieren wir den Informationsfluss im Netzwerk, indem wir Constructor erlauben, die Beschriftungen benachbarter Knoten zu ändern. Als Ziel hat Constructor entweder eine Erreichbarkeits- oder eine Sicherheitsbedingung, d.h., Constructor muss entweder ein zusammenhängendes Netzwerk herstellen oder aber sicherstellen, dass das Netzwerk immer zusammenhängend bleibt. Wir zeigen, unter welchen Bedingungen das Lösen dieser Spiele entscheidbar ist und untersuchen in diesem Fall die Berechnungskomplexität. Die Ergebnisse hängen von den Fähigkeiten von Constructor ab und unterscheiden sich für das Erreichbarkeits- und das Sicherheitsspiel.

Infinite games are a strong model for analyzing dynamic networks that encounter continuous topological changes during operation. In this framework, the players represent the contrary forces which modify the network. In particular, this thesis deals with three different two-player games which focus on guaranteeing routing and connectivity properties in dynamic networks. In each model, one player has to establish the proper operation of the network, while the adversary produces failures and demands that occur during operation. In the first part, we study sabotage games, which van Benthem introduced in 2002. In these games, a Runner traverses a graph and tries to reach a set of goal vertices, while a Blocker removes edges. We refine this game in two ways; namely we consider a more general winning objective expressed in linear temporal logic, and we study the variant in which Blocker is replaced by a probabilistic player. We show that in both cases the problem to decide whether Runner wins remains PSPACE-complete. In the second part, we develop a routing game in which a routing agent has to deliver packets to their destinations, while a demand agent continuously generates packets and blocks connections for a certain amount of time. We show general limitations for obtaining routing strategies but also point to algorithmic solutions. The results depend on both the desired routing property and the coarseness of the model. For certain scenarios we develop feasible routing algorithms, each of which guarantees a routing property against any behavior of the demand agent. In the third part, we introduce a connectivity game between a Constructor and a Destructor. While Destructor deletes nodes, Constructor can restore or even create new nodes under certain conditions. Also, we model information flow through the network by allowing Constructor to change labels of adjacent nodes. Constructor either has a reachability or a safety objective, i.e., Constructor has to either establish a connected network or guarantee that the network always stays connected. We show under what conditions the solvability of these games is decidable and, in this case, analyze the computational complexity. The results depend on the abilities of Constructor and differ for the reachability and the safety version.

Fulltext:
PDF