为什么心跳需要O（log N）时间来传播
问题描述：
我正在阅读关于八卦式失败检测的内容。为什么心跳需要O（log N）时间来传播
在我正在读它的Notes的指出：a single heartbeat takes O(log(N)) time to propagate但这一说法没有解释
任何想法，这是为什么？
答
因为在这种情况下最有效的传播方式是使用二叉树结构（或任何k-ary树）。第一个节点向其子节点发送消息，向其子节点发送消息等。二叉树高度为log n，树中的每个级别代表传播消息的一个阶段，所以总体时间等于O(log n)。
答
您首先发送消息给k个节点。他们每个人都会向k个节点发送消息并收集回复。每跳将接收消息的节点数乘以k。当k^t> = N时，所有节点都收到了这个消息。发生这种情况所花费的时间与跳数成正比。
K^T = N => log_k（N）= T
我们知道，时钟时间正比于T，所以它必须是成比例的log_k（N）。
我并不熟悉八卦，但这个答案适用于大多数群集结构上的大多数广播消息。