[分布式算法] 关于 AsynchBFS 算法的 termination

[lsmgeb89]

Nancy Lynch 的 Distributed Algorithms ，其中讲到 P.503 ~ 504 有关于这个的描述。如下图：

描述： process i 收到 process j 发来的 new dist estimate 后，若比 current dist 小， do relaxation step ，发 search message containing updated dist 给所有非 process j 的 neighbors ，然后等待所有这些 neighbors acknowledge ，要么是 parent ，要么是 non-parent 。

问题： 如果在等待 acknowledge 的过程中， process i 又收到一个新的从 process k 发来的 estimate ，并且比 current dist 小。 process i 怎么处理？

1. process i 立刻发 non-parent 给 process j 并且 clean 前面的 bookkeeping ？

2. process i 继续等完前面的 acknowledge ，再发 non-parent 给 process j ？

如果有 termination 这部分协议的细节就更好了，谢谢！

[lsmgeb89]

@Livid 无人回答，麻烦删贴，谢谢。