V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
lsmgeb89
V2EX  ›  问与答

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

  •  
  •   lsmgeb89 · 2016-11-24 09:41:39 +08:00 · 2408 次点击
    这是一个创建于 2919 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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 这部分协议的细节就更好了,谢谢!

    1 条回复    2016-11-25 00:25:36 +08:00
    lsmgeb89
        1
    lsmgeb89  
    OP
       2016-11-25 00:25:36 +08:00
    @Livid 无人回答,麻烦删贴,谢谢。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1306 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 17:51 · PVG 01:51 · LAX 09:51 · JFK 12:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.