なぜ、ハートビートが伝播するのにO（ログN）時間かかります

Question

ゴシップスタイルの障害検出について読んでいました。私はそれを読んでいたノートで

があると述べています： a single heartbeat takes O(log(N)) time to propagateが、この文は

これは、なぜすべてのアイデアを説明されていませんか？

Answer 1

このような場合の伝播の最も効果的な方法は、バイナリツリー構造（またはk-aryツリー）を使用するためです。最初のノードは子にメッセージを送信し、子にメッセージを送信します。バイナリツリーの高さはlog nです。ツリー内のすべてのレベルは伝播メッセージの1つのステージを表します。したがって、全体の時間はO(log n)になります。

Answer 2

まず、kノードにメッセージを送信します。各ノードはk個のノードにメッセージを送信し、応答を収集します。各ホップは、メッセージを受信したノードの数にkを掛けます。すべてのノードは、k^t> = Nのときにメッセージを受信しました。これが発生するのにかかる時間は、ホップ数tに比例します。 T = N => log_k（N）は我々はそれがlog_k（N）に比例しなければならないので、クロック時間は、Tに比例していることを知っているトン

=^

K。

私は特にゴシップに精通していませんが、この回答はほとんどのクラスタファブリックのほとんどのブロードキャストメッセージに適用されます。