6-Färbung eines Baumes in verteilter Weise

Ich habe einige Schwierigkeiten, den verteilten Algorithmus für Baum 6 zu verstehen - Färbung in -Zeit.$O(\log^*n)$

Die vollständige Beschreibung finden Sie in folgendem Artikel: Parallele Symmetrieunterbrechung in spärlichen Graphen. Goldberg, Plotkin, Shannon .

Kurz gesagt, die Idee ist ...

Ausgehend von der gültigen Färbung, die durch die Prozessor-IDs angegeben wird, reduziert die Prozedur iterativ die Anzahl der Bits in den Farbbeschreibungen, indem jeder Nicht-Wurzelknoten mit der Farbe neu eingefärbt wird, die durch Verketten des Index eines Bits erhalten wird, in dem von abweicht und der Wert dieses Bits. Die Wurzel verkettet und , um ihre neue Farbe zu bilden.$v$$C_v$$C_{parent}(v)$$r$$0$$C_r[0]$

Der Algorithmus wird nach -Iterationen beendet.$O(\log^*n)$

Ich habe nicht das intuitive Verständnis, warum es tatsächlich in -Iterationen endet . Wie in dem Artikel über die letzte Iteration erwähnt, gibt es den kleinsten Index, bei dem sich zwei Bitfolgen unterscheiden, höchstens 3. Das 0. Bit und das 1. Bit könnten also gleich sein und , also ergibt dieses Zwei-Bit 4 Farben + weitere 2 Farben für verschiedene 3. Bits und insgesamt 8 Farben und nicht 6 wie im Papier, und warum wir mit 2 Bits nicht weiter vorgehen können, ist es immer noch möglich, verschiedene Bits zu finden und sie zu trennen.$O(\log^*n)$$2^2=4$

Ich würde mich über eine etwas tiefere Analyse des Algorithmus freuen als in der Arbeit.

$\log^* n$

$\log^* n + 1 = O(\log^* n)$

Hoffe das hilft!

Der verteilte Algorithmus für Baum 6 - Färbung in O (log * (n)) Zeit ist ein sehr guter Algorithmus.

Lassen Sie mich erklären, was "log * n" ist.

log * (n) - "log Star n", bekannt als "Iterierter Logarithmus"

In einfachen Worten können Sie log * (n) = log (log (log (..... (log * (n))) annehmen.

log * (n) ist sehr mächtig.

Beispiel:

1) Log * (n) = 5 wobei n = Anzahl der Atome im Universum

jetzt deine frage:

Warum wird es nach der Anmeldezeit beendet?

In jeder runden Größe der ID, die um den Log-Faktor reduziert wird, verringert sich auch die Anzahl der Farben: zum Indexbit, bei dem sich zwei Beschriftungen der Größe n Bit unterscheiden + 1 weiteres anhängendes Bit.

Warum nur 6 Farben, warum nicht mehr oder weniger?

Warum nicht 4 Farben: {0,1,2,3} - da zwei Bits erforderlich sind, um den Index dort zu adressieren, wo sie sich unterscheiden, und das Hinzufügen des „Differenzbits“ mehr als zwei Bits ergibt.

Warum nicht 7 Farben: {0,1,2,3,4,5,6} - als 7 = 111 (in Binär) kann mit 3 Bits beschrieben werden, und um den Index (0,1,2) zu adressieren, sind zwei Bits erforderlich plus ein „Differenzbit“ ergibt wieder drei.

Warum 6 Farben? - Die Farben 110 (für Farbe „6“) und 111 (für Farbe „7“) werden nicht benötigt, da wir eine weitere Runde machen können! (IDs von drei Bits können sich nur an den Positionen 00 (für „0“), 01 (für „1“), 10 (für „2“) unterscheiden.

Sie können 6-Farben auf 3-Farben reduzieren , was im obigen Link Ihres Kommentars angegeben ist.