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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0901106-181811 |
| Date | 01 September 2006 |
| Creators | Lin, Hsu-Shen |
| Contributors | Shi-Jinn Horng, D. J. Guan, Yi-Hsing Chang, Yue-Li Wang, Chang-Biau Yang |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0901106-181811 |
| Rights | off_campus_withheld, Copyright information available at source archive |
Page generated in 0.0018 seconds