Atomic transaction processing in mobile ad-hoc networks

Abstract

Mobile Ad-Hoc Networks (MANETs) are self-organized wireless networks where mobility and limited energy resources cause frequent communication and node failures. Guaranteeing consistency and integrity of distributed data in such a volatile environment is challenging. A key concept to assure these guarantees are distributed atomic transactions. Transferring this concept to a MANET environment raises several new research questions due to high failure probabilities. This work analyzes blocking risks of distributed transactions in MANETs and provides solutions to control these risks. It is well known that a non-blocking atomic commit protocol cannot exist in presence of communication and node failures. This impossibility has little impact on transaction processing in fixed networks, since communication and node failures are so rare that transaction processing is not significantly affected or delayed; however, the situation in MANETs is not clear. Research has not answered yet which transactions show high blocking risks and how blocking risks are influenced by different transaction models. Therefore, a controlled risk management in MANET transaction processing is not possible yet. This thesis contributes towards a better understanding of atomic transaction processing in MANETs by presenting:

* A probabilistic model to predict the abort and blocking risks for arbitrary transaction and MANET scenarios caused by communication or node failures. The model is used to analyze strict and semantic transaction models.

* A solution to control blocking risks caused by participant failures called Shared Log Space (SLS). The SLS system allows to preserve decision logs of a transaction at a defined availability within a MANET for recovering participants. It is shown how the SLS is embedded in commit processing of strict and semantic transactions and how blocking risks can be decreased to a desired level. Two implementation approaches of the SLS are described and evaluated.

* A probabilistic model to analyze the use of a backup coordinator (BC) to reduce blocking risks caused by a node failure of the transaction coordinator. It is shown that an integration of a BC is not necessarily beneficial but may increase the blocking risk in some situations. The presented probabilistic model allows to identify such situations. Additionally, I propose a scheme to integrate the BC with the SLS to assure a required availability of decision logs if the transaction coordinator fails.

These contributions are fundamental, as they provide a comprehensive model to predict and control blocking risks in MANETs. Such a model is useful as it allows for adaptive risks management during transaction processing, it can be decided whether the use of a more reliable protocol, the SLS or BC, is indicated and to what level blocking risks can be reduced.

Mobile Ad-Hoc Netze (MANETs) sind drahtlose Kommunikationsnetze, die von mobilen Geräten gebildet werden und ohne feste Infrastruktur wie z.B. Basisstationen etc. auskommen. Um die Kommunikation zwischen Knoten zu ermöglichen, die nicht in direkter Kommunikationsreichweite liegen, leitet jedes Gerät Nachrichten für andere weiter. Der ständige Topologiewechsel, die beschränkten Ressourcen (Systemleistung, Energie) der mobilen Netzknoten, mögliche Interferenzen, etc. bedingen eine höhere Wahrscheinlichkeit für Kommunikationsfehler als in festen Netzen. Die unzuverlässigere Kommunikation in MANETs wirft die Frage nach der Datenkonsistenz und Datenintegrität in verteilten Anwendungen in diesem Kommunikationsumfeld auf. Konsistenz und Integrität verteilter Daten werden in festen Netzen mit Hilfe von atomaren verteilten Transaktionen gewährleistet. Die vorliegende Arbeit überträgt diese Methode auf MANET-Umgebungen, analysiert die sich daraus ergebenen Problemstellungen und diskutiert geeignete Lösungsansätze. Insbesondere werden die Abbruch- und Blockierungsrisiken von verteilten Transaktionen untersucht. Dafür werden spezifische Wahrscheinlichkeits- und Simulationsmodelle entwickelt. Da es grundsätzlich nicht möglich ist, Blockierungssituationen vollständig zu verhindern, muss das Blockierungsrisiko überwacht und gegebenenfalls mit entsprechenden Methoden begegnet werden. Zur Lösung dieser Probleme werden folgende Beiträge präsentiert:

* Ein Berechnungsmodell zur Bestimmung der Abbruch- und Blockierungswahrscheinlichkeit von verteilten Transaktionen in MANETs für unterschiedliche Transaktionsmodelle.

* Ein Konzept - der Shared Log Space (SLS) - zur Aufhebung von Blockierungssituationen, die durch Fehler von Transaktionsteilnehmern ausgelöst werden. Der SLS ermöglicht es, den blockierten Knoten die Transaktionsentscheidung mit einer definierten Wahrscheinlichkeit zu kommunizieren und ihren Blockierungszustand zu verlassen. Zwei SLS Implementierungen werden vorgestellt und diskutiert.

* Einführung eines Backupkoordinators zur Reduzierung des Blockierungsrisikos durch Fehler des Transaktionskoordinators, wobei ein Wahrscheinlichkeitsmodell die Berechnung des Blockierungsrisikos bei dessen Verwendung erlaubt. Zusätzlich werden Strategien vorgestellt, um den Backupkoordinator mit dem SLS zu verknüpfen.

Diese Modelle und Methoden sind Vorraussetzung für ein adaptives Risikomanagement während der Transaktionsverarbeitung in MANETs. Die Einführung eines adaptiven Risikomanagements ist sinnvoll, da die Anwendung der in der Arbeit entwickelten Wahrscheinlichkeitsmodelle auf unterschiedliche Transaktions- und Kommunikationsszenarien gezeigt hat, dass nur für ein bestimmtes Spektrum von Transaktionen ein signifikantes Blockierungsrisiko existiert. Diese Transaktionen zu identifizieren und ihr Blockierungsrisiko zu kompensieren ist der grundlegende Beitrag dieser Arbeit.