Seite drucken

TSSSA

Zeit- und speichereffiziente selbststabilisierende Algorithmen

Projektbeschreibung

Selbststabilisierung ist eine Technik, die einem verteilten System die Toleranz beliebiger transienter Fehler ermöglicht. Ein Verfahren ist selbststabilisierend, wenn es aus sich heraus, also ohne äußeres Zutun, nach transienten Fehlern selbsttätig in einen korrekten Zustand zurückkehrt und dann in einem solchen verbleibt.

In der Entwicklung selbststabilisierender Algorithmen steht das Ziel im Vordergrund, die Zeitspanne von einem beliebigen Startzustand bis zur Erlangung eines korrekten Systemzustandes zu minimieren. Dabei wird in Kauf genommen, dass während der Übergangsphase ein beträchtlicher Teil des Netzes seinen Dienst nicht erbringen kann. Zur optimalen Ressourcenausnutzung wird neben der Minimierung des Zeitaufwands bis zur Stabilisierung eines Verfahrens zudem ein möglichst geringer Speicherbedarf angestrebt.

Die Abschätzung der Komplexität selbststabilisierender Algorithmen ist im Allgemeinen nicht trivial. Für viele Verfahren existieren daher nur obere Schranken, die weit von den schlimmsten bekannten Beispielen entfernt sind. Die Analyse von existierenden Algorithmen, um diese Lücken zu schließen, ist neben der Entwicklung eigener Verfahren ein zweiter Schwerpunkt dieses Projekts.

Publikationen

Volker Turau und Bernd Hauck. A new Analysis of a Self-Stabilizing Maximum Weight Matching Algorithm with Approximation Ratio 2. Theoretical Computer Science, 412(40):5527–5540, September 2011. Stabilization, Safety and Security.
@Article{Telematik_HT_2010_TCS_Matching, author = {Volker Turau and Bernd Hauck}, title = {A new Analysis of a Self-Stabilizing Maximum Weight Matching Algorithm with Approximation Ratio 2}, pages = {5527-5540}, journal = {Theoretical Computer Science}, volume = {412}, number = {40}, month = sep, year = 2011, keywords = {Self-stabilizing algorithms, approximation algorithm, weighted matching, distributed algorithms}, issn = {0304-3975}, note = {Stabilization, Safety and Security}, }
Abstract: The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a 2-approximation of the optimal solution. They established that their algorithm stabilizes after O(2^n) (resp. O(3^n)) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis improving these bounds considerably. In particular it is shown that the algorithm stabilizes after O(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after O(nm) moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction to analyze the complexity of self-stabilizing algorithms.
Volker Turau und Bernd Hauck. A fault-containing self-stabilizing (3 - 2/(Delta+1))-approximation algorithm for vertex cover in anonymous networks. Theoretical Computer Science, 412(33):4361–4371, 2011.
@Article{Telematik_HT_2011_TCSVC, author = {Volker Turau and Bernd Hauck}, title = {A fault-containing self-stabilizing (3 - 2/(Delta+1))-approximation algorithm for vertex cover in anonymous networks}, pages = {4361-4371}, journal = {Theoretical Computer Science}, volume = {412}, number = {33}, year = 2011, keywords = {Self-stabilizing algorithms, Fault tolerance, Distributed algorithms, Graph algorithms}, }
Abstract: The non-computability of many distributed tasks in anonymous networks is well known. This paper presents a deterministic self-stabilizing algorithm to compute a 3 - (2 / (Delta+1))-approximation of a minimum vertex cover in anonymous networks. The algorithm operates under the distributed unfair scheduler, stabilizes after O(n+m) moves respectively O(Delta) rounds, and requires O(log n) storage per node. Recovery from a single fault is reached within a constant time and the contamination number is O(Delta). For trees the algorithm computes a 2-approximation of a minimum vertex cover.
Volker Turau. Self-Stabilizing Vertex Cover in Anonymous Networks with Optimal Approximation Ratio. Parallel Processing Letters, 20(2):173–186, 2010.
@Article{Telematik_T_2010_PPL, author = {Volker Turau}, title = {Self-Stabilizing Vertex Cover in Anonymous Networks with Optimal Approximation Ratio}, pages = {173-186}, journal = {Parallel Processing Letters}, volume = {20}, number = {2}, year = 2010, }
Abstract: This paper presents a deterministic self-stabilizing algorithm that approximates a minimum vertex cover in anonymous networks with ratio 2 using the distributed scheduler and the link-register model with composite atomicity. No algorithm with a better approximation ratio can exist. The algorithm stabilizes in O(min{n, Δ², Δ log3 n}) rounds and requires O(Δ) memory per node.
Volker Turau und Bernd Hauck. A Self-Stabilizing Approximation Algorithm for Vertex Cover in Anonymous Networks. In Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'09), Springer, November 2009, pp. 341–353. Lyon, France.
@InProceedings{Telematik_HT_2009_VC, author = {Volker Turau and Bernd Hauck}, title = {A Self-Stabilizing Approximation Algorithm for Vertex Cover in Anonymous Networks}, booktitle = {Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'09)}, pages = {341-353}, series = {Lecture Notes in Computer Science}, volume = {5873}, publisher = {Springer}, day = {3-6}, month = nov, year = 2009, location = {Lyon, France}, }
Abstract: This paper presents a deterministic self-stabilizing algorithm that computes a 3-approximation vertex cover in anonymous networks. It reaches a legal state after O(n+m) moves or 2n + 1 rounds respectively and recovers from a single fault within a constant containment time. The contamination number is 2 Delta + 1. An enhanced version of this algorithm achieves a 2-approximation on trees.
Volker Turau und Bernd Hauck. A Self-Stabilizing Algorithm for Constructing Weakly Connected Minimal Dominating Sets. Information Processing Letters, 109(14):763–767, 2009.
@Article{Telematik_HT_2009_WCMDS, author = {Volker Turau and Bernd Hauck}, title = {A Self-Stabilizing Algorithm for Constructing Weakly Connected Minimal Dominating Sets}, pages = {763-767}, journal = {Information Processing Letters}, volume = {109}, number = {14}, year = 2009, keywords = {Self-stabilizing algorithms, Fault tolerance, Distributed algorithms, Graph algorithms}, issn = {0020-0190}, }
Abstract: This paper presents a new distributed self-stabilizing algorithm for the weakly connected minimal dominating set problem. It assumes a self-stabilizing algorithm to compute a breadth-first tree. Using an unfair distributed scheduler the algorithm stabilizes in at most O(nmA) moves, where A is the number of moves to construct a breadth-first tree. All previously known algorithms required an exponential number of moves.
Bernd Hauck. Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set. Technical Report urn:nbn:de:gbv:830-tubdok-5126, Hamburg University of Technology, Hamburg, Germany, Oktober 2008.
@TechReport{Telematik_Hauck_2008_WorstCaseSelfStabilizingWeaklyConnectedMDSet, author = {Bernd Hauck}, title = {Worst-Case Analysis of a Self-Stabilizing Algorithm Computing a Weakly Connected Minimal Dominating Set}, number = {urn:nbn:de:gbv:830-tubdok-5126}, institution = {Hamburg University of Technology}, address = {Hamburg, Germany}, month = oct, year = 2008, }
Abstract: Recently, Srimani and Xu presented a self-stabilizing algorithm that computes a weakly connected minimal dominating set. They prove an upper bound of O(2^n) until stabilization but they do not provide a lower bound. This paper verifies by giving an example that their algorithm indeed requires O(2^n) moves on a certain graph.
Volker Turau. Linear Self-Stabilizing Algorithms for the Independent and Dominating Set Problems using an Unfair Distributed Scheduler. Information Processing Letters., 103(3):88–93, Juli 2007.
@Article{Telematik_TT_2007_Selfstabilizing, author = {Volker Turau}, editor = {A. Tarlecki}, title = {Linear Self-Stabilizing Algorithms for the Independent and Dominating Set Problems using an Unfair Distributed Scheduler}, pages = {88-93}, journal = {Information Processing Letters.}, volume = {103}, number = {3}, month = jul, year = 2007, }
Abstract: This paper presents distributed self-stabilizing algorithms for the maximal independent and the minimal dominating set problems. Using an unfair distributed scheduler the algorithms stabilizes in at most max{3n-5,2n} resp. 9n moves. All previously known algorithms required O(n2) moves.

Studentische Arbeiten

Abgeschlossene Arbeiten