Diploma Thesis
The principle of selfstabilization is a very general technique to design a distributed system to tolerate arbitrary transient faults. An algorithm is selfstabilizing 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 faultfree 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 selfstabilizing 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 2approximation on trees while the result on arbitrary graphs is only a 3approximation. The goal of this thesis is to analyze the quality of the approximation of several selfstabilizing algorithms considering the structure of the graph on which it is executed. For this purpose a few selfstabilizing 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 worstcase scenarios usually do not comply with installations in practice the theoretical results will be compared with results of a selfwritten simulator.
Start date  25. December 2009 
End date  25. May 2010 
Documents  Flyer 
Projects  TSSSA  SelfStabilization 
Supervisor 
Dr. rer. nat. Bernd Hauck
