4
$\begingroup$

I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10).

Here is a short description

Idea of the algorithm: We start with color labels that have $\log n$ bits. In each synchronous round we compute a new label with exponentially smaller size than the previous label, still guaranteed to have a valid vertex coloring.

Let $i$ be the smallest index where $c_v$ and $c_p$ differ; the new label is $i$ (as a bitstring) followed by the bit $c_v(i)$ itself

Grand-parent 0010110000 -> 10010 -> …
Parent       1010010000 -> 01010 -> 111
Child        0110010000 -> 10001 -> 001

The problem I cannot understand this example. Let's take Grand-parent($c_p$ = 0010110000) and parent($c_v$ = 1010010000), on the round when $c_v$ receives $c_p$, so we need to change $c_v$. They differ in 5th bit, counting from 0 (5 in binary is 101), so according to definition, $c_p$ is "$101$"+$c_p[5]=1010$, but in example it's 01010, what I get wrong?

$\endgroup$
7
$\begingroup$

The labels $c_v$ and $c_p$ are relative. So when a node (parent in your example) having $c_v = 1010010000$ receives from its parent (grandparent in your example) an id $c_p = 0010110000$, the difference, as you correctly point out, is in the fifth position.

Now, the total number of bits in the original ids is 10, so representing any index (0-9) will require 4 bits. So, the new id will have 4 bits from the position difference + 1 bit for the differing bit. Now, $$(5)_{10} = (0101)_2$$

Note, we use 4 bits as discussed above, so that all new ids, can have the same number of bits. Then, $c_v(5) = 0$ is concatenated towards the LSB side, giving the new id: $01010$.

$\endgroup$
  • $\begingroup$ thank you, for explanation, the last point is why in case of parent and child on the second iteration, when $c_p = 01010$ and $c_c= 10001$, 5 digits, differ in 1th bit, so $c_c = 001+0=10$, but it's $001$ $\endgroup$ – com Dec 17 '12 at 12:13
  • $\begingroup$ Yes, I'm pretty sure it should be $000 || 1$ (concatenation) giving $0001$. Unless there is some way to show that after the first iteration, the difference can never be in the most significant bit, in which case you only need to represent indices from 0-3 using 2 bits. But since such a proof is not provided, and since it is safe to assume that the first differing position can also be in the MSB, I would say the safer way (and giving correct results) will be to take 3 bits for the differing index, and the result would be $0001$. $\endgroup$ – Paresh Dec 17 '12 at 13:15

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.