1-Fair Alternator Designs for the de Bruijn Network

by Lin, Hsu-Shen

Abstract (Summary)
An alternator is a self-stabilizing system which consists of a network of concurrent processors. One of its properties is that any two processors of an alternator system cannot execute the critical step at the same time if they are adjacent. This exclusion property transforms the alternator design problem into the coloring problem. And an alternator is said to be 1-fair if no processor executes the critical step twice when one or more other processors have not executed the critical step yet. The simplicity of routing message and the capability of fault tolerance of de Bruijn networks attract us to design 1-fair alternator on them. In this thesis, two algorithms are proposed to solve the coloring problem on the de Bruijn network. The first one uses $2ceil{log_2k}+1$ colors to color the $k$-ary de Bruijn graph with two digits, while the second one uses $p+1$ only colors, where ${{p-1}choose{floor{(p-1)/2}}} < k leq {pchoose{floor{p/2}}}$. We also prove that the second coloring method is optimal when $k = {pchoose{floor{p/2}}}$. In other words, the chromatic number of the $k$-ary de Bruijn graph with two digits is $p+1$, where $k = {pchoose{floor{p/2}}}$. Furthermore, the extension of our coloring method can be applied to the $k$-ary de Bruijn graph with three or more digits.
Bibliographical Information:

Advisor:Shi-Jinn Horng; D. J. Guan; Yi-Hsing Chang; Yue-Li Wang; Chang-Biau Yang

School:National Sun Yat-Sen University

School Location:China - Taiwan

Source Type:Master's Thesis

Keywords:coloring de bruijn graph alternator 1 fair


Date of Publication:09/01/2006

© 2009 All Rights Reserved.