algorithm - 分布式计算中的 LCR vs Floodmax(领导人选举)

Question

我试图了解 LCR 和 Floodmax 在同步网络环境中的实际区别。

我知道 Floodmax 的时间复杂度为 O(N)，其工作原理如下:

• 每个进程都保留它迄今为止看到的最大 UID(最初是它的自己)。
• 在每一轮，每个进程将这个最大值发送给每个即将离任的邻居。
• 如果最大值是进程的 UID，那么在 diam 轮次之后选举自己为领导者，否则为非领导者。

另一方面，LCR:

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

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

Answer 1

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