Distributed and self-stabilizing algorithms for capacitated graph theory problems

Failure of a single element or of a communication medium between more than one elements of a distributed system result in undesired activities toward the common goal of the network. As a nature of distributed algorithms, since the processing elements only have limited (local) information and are independent from each other with respect to the computational powers, these failures are difficult to detect and resolve. Fault tolerant mechanisms which aim at masking the failure so that the fault is not observable to the users of the system are costly in terms of computational resources. On the other hand, the masking constraint can be relaxed in such systems where an undesired behavior of the system is tolerable for a limited time, given that the system is guaranteed to reach a non-faulty and desired state in a foreseeable time. Self stabilization is an important non-masking fault tolerant concept. A self-stabilizing algorithm is a set of rules which are activated and executed in case of an adversarial configuration of the system in such a way that the system eventually reaches a desired configuration in which none of the rules are activated, i.e., system is stabilized. This thesis is a collection of new self-stabilizing algorithms for some of the classical graph theoretical problems. We focus on the capacitated versions of these problems which have not attracted the attention they deserve from the fault tolerance field, even though their real world applications generally come with their own capacity restrictions. We particularly deal with and propose novel self-stabilizing algorithms for capacitated matching (b-matching), capacitated minimum spanning tree (CMST) and capacitated k-way graph partitioning problems. We give formal proofs for the correctness, convergence and closure of this algorithms.