Consistent data replication in mobile ad hoc networks

Abstract

Mobile ad-hoc networks (MANETs) are used in situations where networks need to be deployed immediately but no network infrastructure is available. If MANET nodes have sensing capabilities, they can capture and communicate the state of their surroundings, including environmental conditions or objects in their proximity. If the sensed state information is propagated to a database to build a consistent model of the real world, a variety of promising context aware applications becomes possible. The models and concepts proposed in this dissertation can be applied to cooperatively maintain a model of the state of physical world objects on devices in MANETs. State information may be updated by independent observers either sequentially or concurrently. Applications that read the state of any object from the model multiple times can rely on the guarantee that every successive read operation will read either the same state information or newer state information that has been reported by an observer after the previously read information. The first contribution of this dissertation formalizes these requirements and defines a novel consistency model called update-linearizability. Secondly, it introduces a new class of data replication algorithms that provably guarantees update-linearizability in MANETs without using synchronized clocks on any pair of nodes in the system. The presented algorithms allow executing read and write operations at any time, which provides high availability of data. These properties are even maintained in networks that are temporarily partitioned and where nodes are highly mobile. Finally the dissertation provides a proof that all replicas held in the system eventually converge towards the most recent state information of the physical world objects which they represent.

Mobile Ad-hoc-Netze (MANET) werden in Situationen verwendet, in denen keine Kommunikationsinfrastruktur zur Verfügung steht. Wenn nun die einzelnen Knoten eines MANET mit Sensoren ausgestattet werden, dann können sie damit vielfältige Zustandsinformationen in ihrer direkten Umgebung erfassen und an andere Knoten des Netzes weitergeben. Werden die erfassten Sensordaten in einer (verteilten) Datenbank gesammelt, um ein konsistentes Bild der physischen Welt zu erhalten, können darauf aufbauend viel versprechende kontextbezogene Anwendungen entwickelt werden. Die in dieser Dissertation präsentierten Modelle und Methoden können zur verteilten Verwaltung von Zustandsinformationen physischer Objekte auf den Knoten eines MANET genutzt werden. Dabei können Zustandsinformationen von unabhängigen Beobachtern sequentiell oder nebenläufig beobachtet werden. Anwendungen, die den Zustand eines Objektes mehrfach lesen, bekommen die Garantie, dass jede Leseoperation entweder das Ergebnis der vorangegangen Leseoperation oder einen aktuelleren Wert für diese Objekt zurückliefert. Dabei bezieht sich „aktueller“ auf einen jüngeren Zustand gemäß der chronologischen Reihenfolge, in der die Beobachtungen durch die Sensoren der Beobachter gemacht wurden. Im ersten Teil dieser Dissertation werden die sich ergebenden Anforderungen formalisiert und ein neuartiges Konsistenzmodell, die so genannte Update-Linearisierbarkeit, definiert. Im zweiten Teil der Arbeit wird eine neue Klasse von Datenreplikationsalgorithmen präsentiert, welche die Einhaltung von Update-Linearisierbarkeit ohne Zuhilfenahme synchronisierter Uhren garantiert. Die präsentierten Algorithmen erlauben jederzeit, auch wenn das MANET zeitweise partitioniert ist, das Ausführen von Lese- und Schreiboperationen und gewährleisten damit eine hohe Datenverfügbarkeit. Darüber hinaus wird der Beweis geführt, dass die verwalteten Daten für jedes Objekt jeweils gegen den aktuellsten im System verfügbaren Zustand konvergieren.