分布式算法设计基础

《分布式算法设计基础》由会员分享，可在线阅读，更多相关《分布式算法设计基础（9页珍藏版）》请在金锄头文库上搜索。

1、1分布式算法设计基础分布式算法设计基础第三章第三章通信协议通信协议计算两个结点之间可靠的数据交换，仅有 send 和 receive 命令是不行的，因为通信必须依靠物理媒介进行，必须依靠协议机制。我们在第一章介绍了七层协议作为计算机网络通信系统体系结构的一种设计的渊源，这种设计现在已经成为国际标准化组织推出的标准。协议的主要功能是数据发送和传递，即在一个站点发送信息，在另外的站点接收和投递信息，同时保证数据交换的可靠性。可靠的数据传递包括重复发送那些丢失的消息，拒收的消息，因混淆而校正后的消息，以及重复发送被丢弃的消息副本。为了使协议确保我们收到的信息准确无误，必然要涉及到间接管理的问题，这进

2、一步涉及到初始化和丢弃与连接有关的状态信息。初始化： 打开连接 （占用通信资源）丢 弃： 关闭连接 （释放通信资源）连接管理的困难在于有可能出现情况： 当关闭连接时，一条消息留在了通道内，这就使得在不存在连接的情况下，或下一个连接被打开时，这条消息被接收，干扰了当前连接的正确性。本章讨论两个协议。第一个协议完全是异步的，它属于 OSI 模型的数据链路层。第二个协议设计用于两个站点，它们之间的通信必须经过中间媒介网网络，故它属于 OSI 模型的传输层。它们之间的差别以下列两种方式影响这些协议所要求的功能。 出错考虑两种不同的协议要考虑在传输过程中出现不同种类的错误； 连接管理在分布式计算中，为了

3、在一段很长的时间里连续操作，通常要支持物理连接，而不是反复打开/关闭连接。对第一种协议，由于通信是在固定的一条物理连线上进行，可以不考虑连接管理，但对第二种协议，我们要考虑。消息的断章取义消息的断章取义因为噪声等多方面的原因，消息在传递过程中可能会发生断章取义，但我们可以设想它可以由连接进程检测到。例如，借助奇偶校验或更一般的总和检查机制等。1平衡的滑动窗协议平衡的滑动窗协议协议算法在两个进程 p、q 之间进行，两个进程之间的地位是对等的。进程2p 可以连续地向进程 q 发送邮包，但累积发送给对方 q 尚未接受的邮包的总数受到一个定值的限制，这个定值就是“开窗”的大小。同样，进程 q 可以连续

4、接收来自 p 发送的邮包，但是，累积接收的总量不可能超出 p 已经发送的邮包总量，某个当前阶段累积接收的邮包数量也不能超出 p 已经发送的邮包总量减去 q 自己已经收到的邮包总量，换言之，q 不可能在接收邮包的通道变空时继续接收邮包。理解这个协议算法，首先要了解这个算法的基本思想，然后要记住算法的各个变量，通过反复阅读，实际模拟算法的执行状态来理解算法，最后，通过进一步了解算法的性质来加深对算法的认识。滑动窗协议算法中一些重要变量参数的含义解释：滑动窗协议算法中一些重要变量参数的含义解释：Qp：存放目的地为 p 的邮包的通道；Qq类似。inp：刻画由 p 必须发送给 q 的信息，是 p 的输入

5、，可能为无穷；outp：刻画记录 q 发送给 p 的信息且 p 已经收到的信息。p 可以随机地读访问 inp，而且也可以随机地写访问 outp。sp ：表示 p 仍然期待着从 q 接收的当前最低位的字的序位号，即 p 已经从outp0写到了 outpsp-1，收到了消息 outp0- outpsp-1。：交换邮包，其中 w 是一个数据字，自然数 i 称为邮包的序列号，当邮包由 p 发送给 q 时，就将字 w=inp i传送给 q 。如果我们设定把由 p 发送给 q 的邮包作为对 p从 q 已收到编号为 0i-lp的字的致谢，那么，进程 p 就会领先于 q（事先设定）固定数目为 lp这么多个邮包

6、数发送邮包。lp：进程 p 可以先于 q 发送邮包的领先数，这是一个事先设定的固定数目。ap：表示 p 尚未接收到的已发送字的致谢中编号为最小的字的序位号。这样，编号从 0 到 ap -1 的由 p 发送给 q 的邮包或字，p 知道 q 进程已经收到了。Sp：由 p 发送第 i 个字的通信操作，i 由发送的邮包信息表出。Rp：表示 p 接收一个字的通信操作。Lp：表示丢掉一个目的地为 p 的邮包。要说明协议是正确的，关键是要证明或说明协议满足安全性质和生存性质。 协议要求满足的安全性质实际上就是每个进程仅输出正确的通信数据，而协议 所要求满足的生存性质（即通信系统没有发生死锁）指所有的通信数据

7、最终都 会被发送和投递。3 协议的安全性质协议的安全性质（1） 安全发送和投递安全发送和投递 outp0sp-1 = inq0sp-1 且 outq0sq-1 = inp0sq-1 p 收到的 向 p 发送 右边的含义是类似的 sp个字 的 sp个字 协议的生存性质协议的生存性质（2 2）终会发送和投递）终会发送和投递对每个整数 k0，具有 spk 且 sqk 的形态最终会到达。 协议的不变量（式）协议的不变量（式）算法 3.1 的协议的不变式 P i sp：outpi udef (0p) i sq：outqi udef (0q) Qp w = inq i (i sq+ lq) (1p) Qq

8、 w = inp i (i sp+ lp) (1q) outpi udef outpi = inq i (ap i lq) (2p) outqi udef outqi = inp i (aq i lp) (2q) apsq (3p) aqsp (3q) 下面我们来证明 P P 是算法的一个不变量（式） 。 引理引理 3.13.1 P P 是算法 3.1 的一个不变量（式） 。证明：证明： 参见教材。参见教材。 协议的正确性证明协议的正确性证明所谓协议算法 3.1 的正确性证明实际上是要说明算法确保了安全和生存性 质，即通信中数据不发生错误，每个进程仅输出正确数据，所有的通信数据最 终都会被投递

9、。正如下面的定理 3.2 中所表明的，安全性质隐含在不变量（式） P 中，但生存性质的说明比较困难。 定理定理 3.2 算法算法 3.13.1 满足安全投递要求。满足安全投递要求。 证明证明：(0p)和(2p)蕴涵了 outp0sp-1 = inq0sp-1，而(0q)和(2q)蕴涵了 outq0sq-1 = inp0sq-1，说明 p 发给 q 的信息和 q 收到的消息是一致的，q发送给 p 的消息与 p 从 q 接收的消息也是一致的。 为了证明协议算法的生存性质，我们还需要对算法及其中一些变量作一些 合理性的假设。 在上面的假设前提下，如果下列两个合理性假设得到满足，协议将满足最 终投递要

10、求。 F1 如果一个邮包的发送适用于无穷长的时间（什么时候发送都行） ，那么， 邮包就会无限次地经常被发送； F2 如果同一个邮包被无限次地经常发送，那么，就能无限次地经常收到4此邮包。 F1 保证了如果一直没有收到致谢，那么，就会不断地一而再，再而三地反 复传送，F2 排除了上面的反复发送对方始终收不到的计算情况。引理引理 3.3 P 蕴涵了蕴涵了sp lq ap sq aq + lp sp+ lp) 证明：由证明：由(0p)和(2p)自然有sp lq ap ，从(3p)可得ap sq 成立。由(0q)和(2q)自然有sq aq + lp ，由(3q)自然有aq + lp sp+ lp 成立

11、。 定理定理 3.4 算法算法 3.1 满足最终投递要求。满足最终投递要求。 证明：证明：协议算法 3.1 是不可能发生死锁的，不变式 P 蕴涵了二个进程中的 其中之一能发送包含最低数目位字的邮包，而这些字对另一个进程来说仍然是 尚未收到的。由 F1 和 F2 的假设，这两个进程都将不断地发送新邮包并接收邮 包， 从而一定会满足最终投递要求。所以，算法 3.1 满足最终投递要求。 下面我们先证明一个断言结论，再继续定理的证明。断言断言 3.5 P 蕴涵了由 p 发送给 或者由 q 发送 是可应用的。现在继续定理 3.4 的证明。 在每一次的计算中，sq和 sq 的值随着时间的推移无限次地经常增

12、加。根据 断言 3.5，协议没有终止形态，故每次计算都是无穷的，即时间上没有限制。假 设 C 是一个计算，在这个计算中 sq和 sq的值仅仅是有限次地经常增加，且设p和 q为 C 中产生的这些变化值的最大值，根据断言断言 3.5，在 sp、sq 、ap和 aq分别达到它们最大的值之后，由 p 发送的 或由 q 发 送的 总是可应用的，因此，依 F1，这两个邮包中的一 个被无限次地经常发送，而依 F2，它也将被无限次地经常接收。但随着 p 接收 一个带有序列号 sp的邮包，会引起 sp的值的增加（反过来 q 也一样） ，这就与 sp和 sq都不会再增加值的假设矛盾，故定理 3.4 得到证明。 协

13、议的进一步讨论协议的进一步讨论2基于计时器的协议基于计时器的协议 基于计时器的协议是一种端（结点计算机）对端的协议。前面介绍的滑动窗协议实际上用于点（进程）对点的协议，是一种t-协议的简化形式，该协议具有恢复丢失的消息，防止重复接收和重新对信息定序的能力。 这种协议要考虑两个结点计算机之间建立和关闭通信连接的情况。协议的 说明信息（包括数据传送部分）保存在一个叫做连连接接记录记录的数据结构中，为了打开/关闭连接，我们可以用建立和删除这个数据结构来刻画连接的状态。一个一个 连连接在某个站点上称接在某个站点上称为为是打开的，如果一个是打开的，如果一个连连接接记录记录存在存在。协议算法考虑的一些要点

14、： 一个方向 数据的传送只考虑一个方向，即从 p 到 q，但需要考虑致谢信息。5 单一字接收窗 接收者不会存储任何带有比它预期收到的邮包编号更高（或更大）数字的 数据邮包。只有当下一个到达的邮包是预期接收的数据邮包时，才会接收该邮 包并立即投递。带有较高序列号的数据邮包可能较先到达，先存起来，但必须 是在前面序列号较低的邮包的处理完成之后，才能处理序列号较高的邮包。能 这样做的协议相对比较复杂。端端通信不考虑这种情况。 简化计时假设 使用最小数目的计时器来表示协议。可以假定，只要接收者这一边打开了 连接，那么，接收进程在任何时候都能发送致谢。也可以假设致谢只能在一个 比较小的时间间隔内发送，但这样会使该协议更复杂。 单一字邮包 发送者在每个数据邮包中可以只装一个单个的字。协议是基于计时器的， 进程得访问物理时钟设备，有关系统中时间和计时器我们做下面假设。 全局时间 时间的一种全局度量延伸到了系统中的所有进程，即每一个事件都称为在 一个确切的时间发生，而事件本身均假设持续时间为 0，而且事件发生的那个 时刻系统中的进程是观察不到的。 有界的邮包寿命 一个邮包的寿命由常数 囿界， 称为最大邮包寿命。因此，如果一个 邮包在时间 被发送而在时间 被接收，则 Mp，Mq : 0 (4) M