6-coloring of a tree in a distributed manner 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!