分布式算法
配置、事件(comp, del)
调度是事件的序列。
安全性 、 活跃性条件
容许执行:满足活跃性条件。
同步模型:时间由轮来度量
广播
在同步模型中,在广播算法的每个容许执行里,树中每个距离 pr 为 t 的处理器在第 t 轮里接
收消息 M
Th2.2 当生成树高度为 d 时,存在一个消息复杂度为 n-1,时间复杂度为 d 的同步广播算法。
异步算法:
引理 2.3 在异步模型的广播算法的每个容许执行里,树中每个距离 pr 为 t 的处理器至多在
时刻 t 接收消息 M。
Th2.5 当生成树高为 d 时,存在一个异步的敛播方法,其 msg 复杂性为 n-1,时间复杂度为
d。
广播和敛播算法用途:初始化某一信息请求(广播发布),然后用敛播响应信息至根。
容许的执行:无限的执行
复杂性度量:
时间复杂度
①同步系统:最大轮数,即算法的任何容许执行直到终止的最大轮数。
②异步系统:假设:①节点计算任何有限数目事件的时间为 0;②一条消息发送和接收之间
的时间至多为 1 个时间单位,定义为:所有计时容许执行中直到终止的最大时间(与最大时
刻的距离)。
Flooding 算法构造生成树(在异步算法中):
一收到消息 M 就转发给除 pj 以外的所有邻居。【从 pr 开始,发送 M 到其所有邻居。当 pi
第 1 次收到消息 M(不妨设此 msg 来自于邻居 pj)时,pi 发送 M 到除 pj 外的所有邻居。
】
msg 复杂性:
2m-(n-1)个 msgs。m 是系统中信道总数,它可能多达 n(n-1)/2。
时间复杂性:O(D) D—网直径
Alg2.2 构造生成树
相互确认。发送一个 msg,pi 收到来自 pj,当收到第一个 msg 时,回发 parent,达成子结点
配对,其他均发 reject。
证明:
为何从根能到达每一结点?(连通)
反证:假设某结点在 G 中从 pr 不可达,因网络是连通的,若存在两个相邻的结点 pi 和 pj
使得 pj 在 G 中是从 pr 可达的(以下简称 pj 可达),但 pi 不可达。因为 G 里一结点从 pr 可达
当且仅当它曾设置过自己的 parent 变量(因为收到过 M 返回后 parent 后才会加入到图 G 中,
容许执行,被赋过值),所以 pi 的 parent 变量在整个执行中仍为 nil,而 pj 在某点上已设置
过自己的 parent 变量,于是 pj 发送 M 到 pi(line9),因该执行是容许的,此 msg 必定最终被