TSSSA
Time- and Space-efficient Self-Stabilizing Algorithms
| Contact | Prof. Dr. rer. nat. Volker Turau |
Project Description
The principle of self-stabilization is a very general technique to design a distributed system to tolerate arbitrary transient faults. An algorithm is self-stabilizing if it can start at any possible global configuration and gain consistency in a finite number of steps by itself without any external intervention and remains in a consistent state.
Designing self-stabilizing algorithms focusses on the objective to minimize the time from an arbitrary initial state until reaching a consistent state. In doing so it is accepted that during this stabilization period a considerable part of the network cannot operate properly. To optimize the usage of resources, aside from minimizing the expenditure of time until stabilization of an algorithm low memory requirements are desired.
Estimating the complexity of self-stabilizing algorithms is generally not a trivial task. Hence, for a lot of algorithms there only exist upper bounds that are far from the worst case examples known today. Thus, apart from developing new algorithms, the analysis of existing algorithms is another key issue of this project.
Publications
Volker Turau and 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 and 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,
}
Volker Turau and 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 and 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, October 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, July 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.