Diplomarbeit
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. The state of a consistent respectively fault-free system is defined by a local predicate based on the states of the nodes. An approximation algorithm does not necessarily find the best solution to a given problem but it intends to get close to it. Some of these algorithms even guarantee that their result deviates from the optimal solution only by a specified range.
For many optimization problems in graph theory there are self-stabilizing algorithms that approximate the optimal solution. Examples are algorithms that approximate a maximum weight matching or a minimum vertex cover. The approximation ratio of an algorithm may depend on the graph’s topology, i.e. the algorithm might achieve a 2-approximation on trees while the result on arbitrary graphs is only a 3-approximation. The goal of this thesis is to analyze the quality of the approximation of several self-stabilizing algorithms considering the structure of the graph on which it is executed. For this purpose a few self-stabilizing algorithms have to be selected for analysis. For each of these algorithms the quality of the approximation has to be determined on several graph classes, e.g. on trees, rings, complete graphs, etc.. Determining the algorithms approximation ratio on a specific topology will be accomplished by means of theoretical analysis and will constitute the main part of this thesis. Since the worst-case scenarios usually do not comply with installations in practice the theoretical results will be compared with results of a self-written simulator.
| Startdatum | 25. Dezember 2009 |
| Enddatum | 25. Mai 2010 |
| Dokumente | Flyer |
| Projekte | TSSSA | Selbststabilisierung |
| Betreuer |
Dr. rer. nat. Bernd Hauck
|