TU Darmstadt / ULB / TUbiblio

Perturbation-Resilient Atomic Commit Protocols for Mobile Environments

Ayari, Brahim (2010)
Perturbation-Resilient Atomic Commit Protocols for Mobile Environments.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

The support of distributed atomic transactions is a key requirement for many current mobile applications. Atomicity is a fundamental property ensuring that all nodes reach a consistent outcome. For this, distributed mobile transactions fundamentally require perturbation-resilient atomic commit protocols. This is challenging as mobile environments are typically characterized by frequent network and node perturbations. The environmental constraints on mobile transaction participants and wireless links may increase the resource blocking time of fixed participants. Moreover, frequent node and link failures complicate the design of atomic commit protocols by increasing both the transaction abort rate and resource blocking time. Hence, the deployment of classical commit protocols is not necessarily applicable to distributed mobile environments. Existing protocols ensuring strict atomicity in mobile environments are either bound to very narrow and specific application scenarios or have poor commit rates, high message overhead or a blocking behavior. In order to cope with different application scenarios, we first identify three classes of mobile environments: infrastructure-based, ad-hoc and generic. Furthermore, we consider and comprehensively classify the perturbations of the wireless mobile environment into classes according to their impact on the outcome of commit protocols and on their blocking behavior. To tolerate these perturbation classes, perturbation-tolerant mechanisms are provided. Based on these mechanisms, we develop a family of perturbation-tolerant atomic commit protocols with minimal resource blocking time and optimized transaction commit rates. For the infrastructure-based mobile environment, we propose an approach that decouples the commit of mobile participants from that of fixed participants -- beyond using the strengths of existing approaches. Consequently, the commit set is reduced to a set of entities in the fixed network. Thus, the commit can easily be supported by any traditional atomic commit protocol. For the ad-hoc mobile environment, we present a commit approach that supports a significantly wider range of mobility patterns and partitioning scenarios than existing protocols. Our approach is based on a novel coordination strategy using a flexible preselection of multiple coordinators among the participating nodes. Thus, the failure of a single coordinator is tolerated in the presence of network partitioning. For the generic mobile environment, we develop an approach that takes advantage of accessing the wired infrastructure if available, by choosing reliable infrastructure nodes for coordinating transactions. If the access to the wired infrastructure is unavailable, our approach adapts itself to the resulting ad-hoc environment. We evaluated our framework and the algorithms presented in this thesis via extensive simulations and experiments. They validated the efficiency and scalability of the developed solutions and additionally emphasized their resilience to the considered environmental, network and node perturbations by minimizing resource blocking times and optimizing transaction commit rates. Furthermore, they confirmed the suitability of our solutions to a wide range of mobile applications.

Typ des Eintrags: Dissertation
Erschienen: 2010
Autor(en): Ayari, Brahim
Art des Eintrags: Erstveröffentlichung
Titel: Perturbation-Resilient Atomic Commit Protocols for Mobile Environments
Sprache: Englisch
Referenten: Suri, Prof. Dr. Neeraj ; Koopman, Prof. Dr. Philip
Publikationsjahr: 6 September 2010
Datum der mündlichen Prüfung: 1 September 2010
URL / URN: urn:nbn:de:tuda-tuprints-22740
Kurzbeschreibung (Abstract):

The support of distributed atomic transactions is a key requirement for many current mobile applications. Atomicity is a fundamental property ensuring that all nodes reach a consistent outcome. For this, distributed mobile transactions fundamentally require perturbation-resilient atomic commit protocols. This is challenging as mobile environments are typically characterized by frequent network and node perturbations. The environmental constraints on mobile transaction participants and wireless links may increase the resource blocking time of fixed participants. Moreover, frequent node and link failures complicate the design of atomic commit protocols by increasing both the transaction abort rate and resource blocking time. Hence, the deployment of classical commit protocols is not necessarily applicable to distributed mobile environments. Existing protocols ensuring strict atomicity in mobile environments are either bound to very narrow and specific application scenarios or have poor commit rates, high message overhead or a blocking behavior. In order to cope with different application scenarios, we first identify three classes of mobile environments: infrastructure-based, ad-hoc and generic. Furthermore, we consider and comprehensively classify the perturbations of the wireless mobile environment into classes according to their impact on the outcome of commit protocols and on their blocking behavior. To tolerate these perturbation classes, perturbation-tolerant mechanisms are provided. Based on these mechanisms, we develop a family of perturbation-tolerant atomic commit protocols with minimal resource blocking time and optimized transaction commit rates. For the infrastructure-based mobile environment, we propose an approach that decouples the commit of mobile participants from that of fixed participants -- beyond using the strengths of existing approaches. Consequently, the commit set is reduced to a set of entities in the fixed network. Thus, the commit can easily be supported by any traditional atomic commit protocol. For the ad-hoc mobile environment, we present a commit approach that supports a significantly wider range of mobility patterns and partitioning scenarios than existing protocols. Our approach is based on a novel coordination strategy using a flexible preselection of multiple coordinators among the participating nodes. Thus, the failure of a single coordinator is tolerated in the presence of network partitioning. For the generic mobile environment, we develop an approach that takes advantage of accessing the wired infrastructure if available, by choosing reliable infrastructure nodes for coordinating transactions. If the access to the wired infrastructure is unavailable, our approach adapts itself to the resulting ad-hoc environment. We evaluated our framework and the algorithms presented in this thesis via extensive simulations and experiments. They validated the efficiency and scalability of the developed solutions and additionally emphasized their resilience to the considered environmental, network and node perturbations by minimizing resource blocking times and optimizing transaction commit rates. Furthermore, they confirmed the suitability of our solutions to a wide range of mobile applications.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Die Unterstützung verteilter atomarer Transaktionen ist eine entscheidende Voraussetzung für viele aktuelle mobile Applikationen. Atomizität ist eine grundlegende Eigenschaft, die gewährleistet, dass alle Knoten ein konsistentes Ergebnis erreichen. Um die Atomizität verteilter mobiler Transaktionen gewährleisten zu können, bedarf es störungsresistenter Commit-Protokolle, da mobile Umgebungen typischerweise durch häufige Netzwerk- und Knotenstörungen gekennzeichnet sind. Die umgebungsbedingten Beschränkungen bei mobilen Transaktionsteilnehmern und drahtlosen Verbindungen können die Ressourcen-Blockierungszeit von drahtgebundenen stationären Teilnehmern erhöhen. Darüber hinaus erschweren häufige Knoten- und Verbindungsfehler die Anwendung konventioneller atomarer Commit-Protokollen durch die Erhöhung sowohl der Transaktionsabbruchrate als auch der Ressourcen-Blockierungszeit der Transaktion. Daher ist der Einsatz klassischer Commit-Protokolle für verteilte mobile Umgebungen als nicht empfehlenswert zu erachten. Bestehende Protokolle, die eine strikte Atomizität in mobilen Umgebungen gewährleisten, sind entweder an sehr begrenzte und spezifische Anwendungsszenarien gebunden oder gehen mit niedrigen Commit-Raten, hohem Nachrichten-Overhead oder Blockierungsverhalten einher. Um die Anwendbarkeit in unterschiedliche Szenarien sicherzustellen, identifizieren wir zunächst drei Klassen von mobilen Umgebungen: Infrastruktur-basiert, ad-hoc und generisch. Des Weiteren klassifizieren wir mögliche Störungen der drahtlosen mobilen Umgebung entsprechend ihrer Auswirkung auf das Ergebnis der Commit-Protokolle und auf deren Blockierungsverhalten. Um diese Störungsklassen zu tolerieren, sind störungstolerante Mechanismen vorgesehen. Basierend auf diesen Mechanismen und unter Berücksichtigung der identifizierten Anwendungsszenarien entwickeln wir eine Familie von störungstoleranten atomaren Commit-Protokollen mit minimaler Ressourcen-Blockierungszeit und optimierten Transaktions-Commit-Raten. Für die Infrastruktur-basierte mobile Umgebung schlagen wir einen Ansatz vor, der die Transaktionsausführung mobiler Teilnehmer von der stationärer Teilnehmer entkoppelt und der zwar die Stärken bestehender Ansätze subsumiert, dabei aber über die einfache Verwendung dieser Ansätze hinausgeht. Dabei reduziert sich das Commit-Set zu einem Set von Einheiten im Festnetz und es können traditionelle atomare Commit-Protokolle leicht eingesetzt werden. Für die Ad-hoc-Umgebung präsentieren wir einen Ansatz, der eine wesentlich breitere Reihe von Mobilitätsmustern und Partitionierungsszenarien als die bestehenden Protokolle unterstützt. Unser Ansatz basiert auf einer neuen Koordinierungsstrategie mit einer flexiblen Vorauswahl von mehreren Koordinatoren unter den beteiligten Knoten. So kann der Ausfall eines einzigen Koordinators, z.B. bei einer Netzwerk-Partitionierung, toleriert werden. Für die generische Umgebung entwickeln wir einen Ansatz, der den Zugriff auf die drahtgebundene Infrastruktur, falls vorhanden, nutzt, indem zuverlässige Infrastruktur-Knoten für die Koordinierung der Transaktionen ausgesucht werden. Wenn der Zugriff auf die drahtgebundene Infrastruktur nicht verfügbar ist, passt sich unser Ansatz an die daraus resultierende Ad-hoc-Umgebung an. Unser entwickeltes Framework und die in dieser Arbeit vorgestellten Algorithmen wurden durch umfangreiche Simulationen und Experimente evaluiert. Die Evaluationsergebnisse demonstrieren die Effizienz und Skalierbarkeit der entwickelten Lösungen und bestätigen ihre Widerstandsfähigkeit gegenüber Netzwerk-und Knoten-Störungen durch Minimierung der Ressourcen-Blockierungszeiten und Optimierung der Transaktions-Commit-Raten. Darüber hinaus zeigen die Ergebnisse die Eignung unserer Lösungen für eine breite Reihe von mobilen Anwendungsszenarien.

Deutsch
Freie Schlagworte: Transaction Commit, Atomicity, Data Consistency, Mobile Database Systems, Perturbations, Dependability, Mobile Environment
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik > Zuverlässige Eingebettete Softwaresysteme
20 Fachbereich Informatik
Hinterlegungsdatum: 13 Sep 2010 14:12
Letzte Änderung: 05 Mär 2013 09:38
PPN:
Referenten: Suri, Prof. Dr. Neeraj ; Koopman, Prof. Dr. Philip
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 1 September 2010
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen