6 colores de un árbol de forma distribuida

Tengo algunas dificultades para comprender el algoritmo distribuido para el árbol 6: colorear en $O(\log^*n)$ hora.

La descripción completa se puede encontrar en el siguiente artículo: Simetría paralela : ruptura en gráficos dispersos. Goldberg, Plotkin, Shannon .

En resumen, la idea es ...

A partir de la coloración válida dada por las ID del procesador, el procedimiento reduce iterativamente el número de bits en las descripciones de color al volver a colorear cada nodo no raíz $v$ con el color obtenido al concatenar el índice de un bit en el que $C_v$ difiere de $C_{parent}(v)$y el valor de este bit. La raíz$r$ concatena $0$ y $C_r[0]$ para formar su nuevo color.

El algoritmo termina después de $O(\log^*n)$ iteraciones

No tengo la comprensión intuitiva de por qué realmente termina en $O(\log^*n)$iteraciones Como se menciona en el documento sobre la iteración final, el índice más pequeño en el que difiere la cadena de dos bits es como máximo 3. Entonces, el bit 0 y el bit 1 podrían ser lo mismo y$2^2=4$, por lo que estos dos bits nos darán 4 colores + otros 2 colores para 3 bits diferentes, y en total 8 colores y no 6 como en el papel, y por qué no podemos continuar con 2 bits, todavía es posible encontrar diferentes bits y sepáralos.

Agradecería un análisis un poco más profundo del algoritmo que en el documento.

En el artículo, los autores mencionan que después $\log^* n$iteraciones, el número de bits utilizados para codificar cualquiera de las etiquetas de color es como máximo 3. Eso significa que hay como máximo ocho colores. Si tenemos seis colores o menos, ya hemos terminado, y de lo contrario volveremos a pasar por el ciclo.

Digamos que hacemos una última iteración de bucle. La raíz obtiene la etiqueta de color 0 o 1. Todos los demás nodos obtienen una etiqueta igual a la posición del primer bit donde la etiqueta anterior de ese nodo no está de acuerdo con la etiqueta de su padre, más un bit adicional. Dado que al ingresar a esta iteración, todos los colores tienen una longitud de tres bits en el peor de los casos, hay tres posiciones posibles donde los bits podrían estar en desacuerdo. Por lo tanto, cada nuevo color se forma a partir de una combinación de una de tres opciones y un bit (una de dos opciones), por lo que al salir de esta iteración de bucle solo hay seis etiquetas de color posibles, por lo que tenemos un color de seis. El número total de iteraciones de bucle es entonces$\log^* n + 1 = O(\log^* n)$

¡Espero que esto ayude!

Algoritmo distribuido para el árbol 6: la coloración en el tiempo O (log * (n)) es un algoritmo muy bueno.

Déjame explicarte qué es "log * n"

log * (n): "log Star n", conocido como "logaritmo iterado"

En palabras simples, puede suponer log * (n) = log (log (log (..... (log * (n)))))

log * (n) es muy poderoso.

Ejemplo:

1) Log * (n) = 5 donde n = Número de átomos en el universo

ahora tu pregunta:

¿Por qué termina después de log * n time?

En cada tamaño redondo de la ID reducida por el factor de registro, por lo tanto, el número de color también se reduce: al bit de índice donde dos etiquetas de tamaño n bit difieren + 1 bit adicional.

¿Por qué solo 6 colores, por qué no más o menos?

¿Por qué no 4 colores: {0,1,2,3}? Ya que se requieren dos bits para direccionar el índice donde difieren, además de agregar el "bit de diferencia" da más de dos bits.

Por qué no 7 colores: {0,1,2,3,4,5,6} - como 7 = 111 (en binario) se puede describir con 3 bits, y para direccionar el índice (0,1,2) requiere dos bits , más un "bit de diferencia" da tres de nuevo.

¿Por qué 6 colores? - los colores 110 (para el color “6“) y 111 (para el color “7“) no son necesarios, ¡ya que podemos hacer otra ronda! (Las ID de tres bits solo pueden diferir en las posiciones 00 (para "0"), 01 (para "1"), 10 (para "2").

puede reducir 6 colores a 3 colores , que se proporciona en el enlace anterior de su comentario.