Ich las über Klatsch Stil Fehlererkennung.Warum dauert ein Herzschlag O (log N) Zeit zu propagieren
In den Notizen, die ich es liest wurde festgestellt, dass: a single heartbeat takes O(log(N)) time to propagate aber diese Aussage erklärt nicht
Jede Idee, warum das so ist?
Da die effektivste Art der Propagierung in diesem Fall die Verwendung der binären Baumstruktur (oder eines beliebigen k-ary-Baums) ist. Der erste Knoten sendet eine Nachricht an seine Kinder, sie senden eine Nachricht an ihre Kinder usw. Der binäre Baum hat eine Höhe von log n, jede Ebene in dem Baum repräsentiert eine Stufe von sich ausbreitenden Nachrichten, so dass die Gesamtzeit gleich O(log n) ist.
Sie beginnen mit dem Senden von Nachrichten an k Knoten. Jeder von ihnen sendet eine Nachricht an k Knoten und sammelt ihre Antworten zurück. Jeder Sprung multipliziert die Anzahl der Knoten, die die Nachricht empfangen haben, mit k. Alle Knoten haben die Nachricht empfangen, wenn k^t> = N ist. Die Zeit, die dafür benötigt wird, ist proportional zu t, der Anzahl der Hops.
k^t = N => log_k (n) = t
Wir wissen, dass die Taktzeit t proportional ist, so dass es zu log_k (N) proportional sein muß.
Ich bin nicht vertraut mit Klatsch im Besonderen, aber diese Antwort gilt für die meisten Broadcast-Nachrichten auf den meisten Cluster-Fabrics.