0

我试图在同步网络的背景下了解 LCR 和 Floodmax 之间的实际区别。

我知道 Floodmax 的时间复杂度为 O(N)，本质上的工作原理如下：

  • 每个进程都保持它迄今为止看到的最大 UID（最初是它自己的）。
  • 在每一轮中，每个进程都会将此最大值发送给每个传出邻居。
  • 如果最大值是进程的 UID，则在 diam 回合之后，它会选举自己为领导者，否则它是非领导者。

另一方面，LCR：

  • 每个进程在环周围发送其 UID。当一个进程收到一个 UID 时，它会将这个 UID 与它自己的进行比较。
  • 如果传入的 UID 更大，那么它将这个 UID 传递给下一个进程。
  • 如果传入的 UID 较小，则将其丢弃。
  • 如果相等，则该进程将自己声明为领导者。

它的时间复杂度也为 O(N)。因此，从本质上讲，这两种算法都在令牌环网络中传递 UID。两者之间有什么真正的区别或优势吗？

4

1 回答 1

2

顾名思义，FloodMax 算法用消息“淹没”网络。与 LCR 不同，即使网络拓扑不是环形，FloodMax 也能正常工作。FloodMax 算法的先决条件是必须知道网络直径（对于 LCR，情况并非如此），并且具有直径轮次的时间复杂度。另一方面，LCR 不需要知道网络直径：因此，它需要额外的通信开销，因为领导者需要通知所有其他进程在它选择自己后终止。

于 2013-01-21T20:16:53.163 回答