SA17011125+吴燕晶+分布式算法1
需积分: 0 22 浏览量
2022-08-08
18:38:27
上传
评论
收藏 18KB DOCX 举报
分布式算法
EX1. 对于 s 的每一次执行的每一个配置都成立的断言 p，则 p 是不是就是不变式？
解：不是。证明如下：我们假设有一个断言 P 它不是不变式，但是它可以由不变式 Q 导出。
我们知道对于不变式 Q，Q=>P，则 P 在 S 的每一次执行的每一个配置中都成立。这样 P 就符
合了以上的条件，但是Ｐ不是不变式，得证。
EX2. 分析在同步和异步模型下，convergecast 算法的时间复杂性
（1）在同步模型下，在每个容许执行中，高度为 d 的生成树的根节点会在 d 轮收到所有节
点的消息。证明如下：
当 d=1 时，根节点会在第一轮收到它的所有孩子节点的信息，所以结论成立。
假设 t<=d-1 时，上述定理成立。
则第 d 轮时，由上述假设我们可知，在第 d-1 轮中，高度为 d-1 的子树收到它的所有节
点的消息。高度为 d-1 的子树的根节点是高度为 d 的根节点的孩子节点，因此它们所收集的
信息只需要一轮就可以传送到高度为 d 的树的根节点，也就是说高度为 d 的生成树的根节点
会在 d 轮收到所有节点的消息。
综述所述上述定理成立。
（2）在异步模型下，在每个容许执行中，高度为 d 的生成树的根节点会在至多 d 时间内收
到所有节点的消息。
当 d=1 时，树由根节点和它的孩子节点组成，由异步模型易知，根节点至多只需要 1 个
单位时间就可以收集到所有节点的信息，所以上述定理成立。
假设 t<=d-1 时，上述定理成立。
当树的高度为 d 时，由上述假设可知，当树的高度为 d-1 时，它收集到所有子节点的消
息的时间至多为 d-1 个单位时间，而能构造高度为 d-1 的树的节点都是高度为 d 的根节点的
孩子节点。由异步模型易知，从孩子节点到根节点至多只需要 1 个单位时间，所以从根节点
到所有节点至多只需要 d 时间就可以收集到所有节点的消息。
EX3. 证明 Pr 可达当且仅当它曾设置过自己的 parent 变量。
证明：充分性：因为 Pr 是可达的，所以它收到了消息 M，所以它执行了算法 2.2 的第五行 upon
receiving M from neighbor Pj，因此它就会执行第七行将 parent 变量进行赋值。必要性：
因为 Pr 曾经设置过自己的 parent 变量，所以它执行了第七行代码，要执行第七行代码必须
要执行第五行代码，也就是说它必须要收到消息 M,而消息 M 是从 Pr 发出的，所以是 Pr 可
达的。
评论0