我正在阅读有关八卦式故障检测的信息。
在我正在阅读的笔记中指出：a single heartbeat takes O(log(N)) time to propagate但未解释此声明
知道这是为什么吗？
2 回答
2
因为在这种情况下最有效的传播方式是使用二叉树结构（或任何 k-ary 树）。第一个节点向其子节点发送消息，他们向其子节点发送消息等。二叉树的高度为log n，树中的每一级代表一个传播消息的阶段，因此总时间等于O(log n)。
于 2017-04-21T09:35:09.423 回答
1
您首先向 k 个节点发送消息。他们每个人都向 k 个节点发送一条消息并收集他们的响应。每跳将接收到消息的节点数乘以 k。当 k^t >= N 时，所有节点都收到了消息。发生这种情况所需的时钟时间与 t（跳数）成正比。
k^t = N => log_k(N)=t
我们知道时钟时间与t成正比，所以它一定与log_k(N)成正比。
我特别不熟悉八卦，但这个答案适用于大多数集群结构上的大多数广播消息。
于 2017-04-21T09:42:14.230 回答