Abstract
A self-stabilizing system is a fault-tolerant distributed network. When it encounters transient faults, including leave/join of nodes or hardware breakdown, it is onceptually brought into an arbitrary initial configuration. It then always manages to return to legitimate configurations without human intervention and resumes operations. For being able to spontaneously fix itself, a self-stabilizing algorithm is also autonomous, scalable, and adaptable. In this dissertation, we study the well-known coloring problems in self-stabilizing systems. We propose three coloring algorithms, one for the vertex coloring problem and the other two for the edge coloring problem. The first one quickly 7-colors planar networks; its time complexity is O(log n), where n is the number of nodes. The second one (Delta + 4)-edge colors planar networks; its time complexity is O(n^2), where Delta is the maximum degree of the nodes. The third one Delta-edge colors bipartite networks; its time complexity is O(kn^2m+m), where k is the number of edges not properly colored in the initial configuration and m is the number of edges. Thus, it finds optimal edge colorings. In addition, it has a property similar to time-adaptive stabilization or superstabilization because its time complexity depends on the quality of the initial configuration. We also study the planarization problem and propose an algorithm that planarizes complete bipartite networks. By not forming a subdivision of K5 or K3,3, the algorithm finds spanning planar graphs in O(n) time, where K5 is a complete graph and K3,3 is a complete bipartite graph. It can further combine with coloring algorithms for finding partial colorings for the networks.