我正在阅读有关八卦样式失败检测的信息。
在我正在阅读的注释中说：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(成比例。
我不特别熟悉八卦，但此答案适用于大多数集群面料上的大多数广播消息。