Self-stabilizing algorithms for the distance-k coloring problem

Abstract

Many problems of practical interest can be modeled as coloring problems. For example, when you are making a phone call using a mobile phone, it needs to transform the voice signal into an electronic wireless signal. Eachsuch signal requires a specific frequency. If two mobile phones close to each other are using the same frequency they could interfere with each other and disrupt the signals. If we assign colors to the different frequencies it is easyto see that a coloring of the phones where phones close to each other receivedifferent colors solves the frequency assignment problem.The coloring problem can easily be generalized so that one requires that units (or phones) within a certain closeness of each other have to receive different colors. One such generalization is the k-coloring problem where weview the units as being connected in a graph and where units within distance k, for some k > 0 must have different colors.In my thesis I investigate self-stabilizing algorithms to solve the distance-k coloring problem. The reason for using a self-stabilizing algorithm is becauseit is an attractive approach when dealing with fault tolerance in distributedsystems. It provides a way to recover from faults without the costand inconvenience of human intervention: after a fault is diagnosed, onesimply has to repair the faulty components, and the system, by itself, will return to a good global state within a relatively shortamount of time.In my work I investigate how existing self-stabilizing algorithms forproviding distance-k knowledge in general networks can be combined withcoloring algorithms to produce a self-stabilizing k-coloring algorithm. This approach is feasible but will require excessiveamounts of memory. Thus I design a distance-2 coloring algorithm that only requires five variables stored in each node. This distance-2 coloring algorithmcan only guarantee to solve the distance-2 coloring problem,but both the number of different colors and the value of the highestcolor could be high. We therefore give an improved distance-2 coloringalgorithm that limits the number of colors. This algorithmrequires eight variables stored in each node.