computer-science - 难以理解伯克利算法

Question

我一直在阅读并努力思考 Berkeley Algorithm .

Berkeley 算法告诉我们，leader 会时不时地询问所有其他进程它们当前的时间，计算所有这些时间的平均值，并向每个进程发回一个 delta 值，即差值在该过程的时间与平均值之间。

例如，考虑一个包含进程A、B 和C 的三进程系统，即A领导人。

现在，如果我是正确的，人们应该期望如果 B 的漂移值为 0.001(也就是说，它每 1000 秒只跳动 999 次)并且我想确保没有进程失调超过 0.1 秒，我会说必须每 100 秒强制时钟同步一次。这意味着我使用的表达式是

存在:

• delta_t 允许我在同步之前等待的最长时间再次计时；
• delta 最大时钟误差； rho漂移率；
• rho = 漂移

我的问题是，在我教授的笔记中，可以找到以下表达式:

也可以在其他文献来源中找到。谁能解释一下为什么我们在第二个表达式中有那个 2？我不确定这些变量是否真的是我假设的那样。

谢谢

Answer 1

(小声明:我没做过分布式计算，可能是我理解错了问题，不如问问教授？)

我认为除以二是为了解释几个过程的正漂移和负漂移。

如果您的最坏情况漂移是 0.001，请考虑 B 有漂移 +0.001 并且 C 有 -0.001。如果您根据初始公式选择 delta-t，B 和 C 之间的时间差可能会是 的两倍同步前你想要的增量。