1-Fair Alternator Designs for the de Bruijn Network
Hsu-shen Lin, Chang‐Biau Yang, Kuo-Tsung Tseng · 2006
In a 1-fair alternator of a network of concurrent processors, no processor executes the critical step twice when one or more other processors have not executed the critical step yet. In this paper, two algorithms are proposed to solve the coloring (1-fair alternator design) problem on the de Bruijn network. The first one uses 2 lceillog2krceil +1 colors to color the k-ary de Bruijn graph with two digits, while the second one uses p + 1 only colors, where (lfloor(p-1)/2rfloorp-1lfloorp/2rfloorp. The second coloring method is optimal when k =lfloorp/2rfloorp. Furthermore, the extension of our coloring method can be applied to the k-ary de Bruijn graph with three or more digits