I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time.

The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse Graphs. Goldberg, Plotkin, Shannon.

In short, the idea is ...

Starting from the valid coloring given by the processor ID's, the procedure iteratively reduces the number of bits in the color descriptions by recoloring each nonroot node $v$ with the color obtained by concatenating the index of a bit in which $C_v$ differs from $C_{parent}(v)$ and the value of this bit. The root $r$ concatenates $0$ and $C_r[0]$ to form its new color.

The algorithm terminates after $O(\log^*n)$ iterations.

I don' have the intuitive understanding why it's actually terminates in $O(\log^*n)$ iterations. As it's mentioned in the paper on the final iteration there is the smallest index where two bit string differs is at most 3. So 0th bit and 1th bit could be the same and $2^2=4$, so this two bit will give us 4 colors + another 2 colors for different 3th bit, and in total 8 colors and not 6 like in the paper, and why we cannot proceed further with 2 bits, it's still possible to find different bits and separate them.

I would appreciate a little bit deeper analysis of the algorithm than in the paper.


In the paper, the authors mention that after $\log^* n$ iterations, the number of bits used to encode any of the color labels is at most 3. That means that there are at most eight colors. If we have six or fewer colors, we're done, and otherwise we go through the loop once more.

Let's say that we do one last loop iteration. The root gets the color label 0 or 1. Every other node gets a label equal to the first bit position where that node's old label disagrees with its parent's label, plus one extra bit. Since on entry to this iteration all colors are three bits long in the worst case, there are three possible positions where the bits could disagree. Therefore, each new color is formed from a combination of one of three choices and a bit (one of two choices), so at exit of this loop iteration there are only six possible color labels, so we have a six-coloring. The total number of loop iterations is then $\log^* n + 1 = O(\log^* n)$

Hope this helps!


Distributed Algorithm for tree 6 - coloring in O(log* (n)) time is very good algorithm.

Let me explain what is "log* n"

log* (n)- "log Star n" as known as "Iterated logarithm"

In simple word you can assume log* (n)= log(log(log(.....(log* (n))))

log* (n) is very powerful.


1) Log* (n)=5 where n= Number of atom in universe

now your question:

Why it terminate after log*n time?

In each round size of the ID reduced by log factor hence the number of color is also reducing: to index bit where two label of size n bit differ + 1 more appending bit.

Why only 6 colors, why not More or Less?

Why not 4 colors: {0,1,2,3} - as two bits are required to address index where they differ, plus adding the “difference-bit“ gives more than two bits.

Why not 7 colors: {0,1,2,3,4,5,6} - as 7=111 (in Binary) can be described with 3 bits, and to address index (0,1,2) requires two bits, plus one “difference-bit“ gives three again.

Why 6 Colors?- colors 110 (for color “6“) and 111 (for color “7“) are not needed, as we can do another round! (IDs of three bits can only differ at positions 00 (for “0“), 01 (for “1“), 10 (for “2“).

you can reduce 6-color to 3-color, which is given in above link of your comment.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.