Dhama, Abhishek (2013) A compositional framework for Designing self-stabilizing distributed algorithms. PhD, Universität Oldenburg.

[img]
Preview
- Accepted Version

Volltext (1221Kb)

Abstract

The proliferation of numerous computing devices in the various facets of life has remarkably elevated the premium placed on fault tolerance of the algorithms running on such devices. Self-stabilization is a novel method to provide non-masking fault tolerance. A distributed system is said to be self-stabilizing if and only if 1) it reaches a closed set of legal states in finite time, and 2) does not leave this set voluntarily. However, designing and proving convergence of a self-stabilizing system is not easy. We investigate whether the conditions under which component algorithms are self-stabilizing can be transcended while composing them. To that end, this dissertation presents a suite of compositional methods which can be used to compose self-stabilizing algorithms, though component algorithms themselves might be self-stabilizing under mutually incompatible conditions.

["eprint_fieldname_title_plus" not defined]

Ein kompositionelles Rahmenwerk für einen Entwurf von selbststabilisierenden verteilten Algorithmen

["eprint_fieldname_abstract_plus" not defined]

Die zunehmende Verwendung verteilter Systeme im alltäglichen Leben für sicherheitskritische Anwendungen stellt besondere Anforderungen an deren Zuverlässigkeit. Stabilisierungstechniken werden in diesem Zusammenhang dazu genutzt, nicht-maskierende Fehlertoleranz einzuführen. Ein System ist selbststabilisierend genau dann, wenn, unabhängig vom initialen Zustand gewährleistet ist, dass das System mit endlich vielen Schritten den legalen Zustandsraum erreicht und diesen ohne Fremdeinwirkung nicht mehr verlässt. Obwohl Selbststabilisierung eine wünschenswerte Eigenschaft für verteilte Algorithmen ist, ist die Beweisbarkeit dieser Eigenschaft nicht trivial. Diese Dissertation befasst sich mit der Entwicklung eines kompositorischen Rahmens für den Entwurf selbststabilisierender verteilter Algorithmen. Die kompositorische Rahmen ausnutzt das Wissen der Ranking-Funktion, die verwendet werden, um die Konvergenz einer Komponente Algorithmus unter seiner ursprünglichen Scheduler zu beweisen.

Item Type: Thesis (PhD)
Uncontrolled Keywords: Fault Tolerance, Distributed Algorithms, Self-Stabilization, Compositional Design, Non-Masking Fault Tolerance
Subjects: Generalities, computers, information > Computer science, internet
Divisions: School of Computing Science, Business Administration, Economics and Law > Department of Computing Science
Date Deposited: 13 Aug 2013 11:50
Last Modified: 13 Aug 2013 11:50
URI: https://oops.uni-oldenburg.de/id/eprint/1588
URN: urn:nbn:de:gbv:715-oops-16690
DOI:
Nutzungslizenz:

Actions (login required)

View Item View Item

Document Downloads

More statistics for this item...