Return to search

1-Fair Alternator Designs for the de Bruijn Network

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.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0901106-181811
Date01 September 2006
CreatorsLin, Hsu-Shen
ContributorsShi-Jinn Horng, D. J. Guan, Yi-Hsing Chang, Yue-Li Wang, Chang-Biau Yang
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0901106-181811
Rightsoff_campus_withheld, Copyright information available at source archive

Page generated in 0.0018 seconds