【精品】分布式算法设计基础(第十章).doc
8页
分布式算法设计基础第10章快照0.引言对运行在计算机网络上的一个基木计算程序(或算法)进行观察，了解各个结 点当前计算的状态，是一项有意义的活动，同时也是一件困难的事情，需要-•种 称Z为快照的技术所谓快照，就是分布式算法在执行中可能达到的一个形态，它是由各个进程 的瞬间状态和通道的瞬间状态拼起来形成的…个全局状态从初始形态岀发，系 统的一个形态可以是分布式算法可能到达的一个形态，也可能是分布式算法永远 不可能达到的一个形态前者可能在某次运行中出现，是一个有意义的快照，后 者无论算法运行多少次，也是不可能达到的形态，是没有意义的形态一些应用引起了快照，例如：(1) 稳定性质：探测当前网络各个结点的计算是否已经进入停滞的稳定状 态，用于离线分析；算法的一个形态丫的一个性质P是稳定的，如果P(/) A/ — 5*P(5)(2) 容错计算：判断当前各结点计算是否出错，以及提供如何排错和避错的 有用信息，可以让算法在快照处重新计算，从而实现容错计算；⑶调试分布式程序：探测各结点进程在程序调试运行中的结果，辅助程序 的运行和调试；本章的主要任务是：针对一个分布式算法，如何获得该算法有意义的快照 实际上，我们也可以认为，一个分布式算法的一个快照是由取自各个进程的局部 状态(局部快照)、通道的状态拼装而成的。
1. 基本概念Ev：设C是由进程P组成的一个分布式系统的一个计算，该计算的事件集 合记为Evo令C是一个分布式系统的计算，它是由一个进程的集合P组成的计算中 事件的集合用巴,表示关丁进程间的通信，我们取弱公平假设：每条消息都将 在有限的时间内收到，而且网络是强连通的进程P的局部计算是由进程的状态 序列叩,叩,...组成的，其中cj是进程p的初始状态以后，我们用进程"的事件叩的出现来标记从到cj的变迁因此，E产U^p{Q），叩，叩，……）在进程〃的事件中，定义局部因果序关系如下：V〃叩 O 0一个全局快照厂由P中每个进程p的快照状态c；组成，我们记 S" = （c；，…,c；） o快照S*中通道pq的状态定义为消息send；q \ rcvd爲的集合形 态/由快照状态和上而定义的通道状态组成send*网：由p发送给q的消息列表;fcvcTpq :由q收到的p发送的消息列表；定义10・0如果在一个全局快照S（J ,・・・,c； ,・・,；“）中，进程P的快照为 叩，即卩是在事件叩和帯之间取快照，则满足疋啲事件叩称为快照前事 件；如果在一个全局快照SNc；,...,中，进程"的快照为C；：）,即”是 在事件4）和叮“Z间取快照，则满足i的事件称为快照后事件。
由以上定义不难得知，在构造一个快照时，如果一条消息的发送事件是一个 快照后事件，而它对应•的接收事件是快照前事件，则所取得的快照是没有意义的 因为，任何一个算法的一个可以到达的有意义的形态，一定不会出现一个进程收 到了另外一个进程尚未发送的消息在P210图10・2中，所取的快照是没有意义 的，因为进程卩2取得的局部快照状态表明，卩2收到了一条在进程门的快照状态 尚未发送的消息，这是不可能的，说明分布式算法不可能出现这样一种形态定义10.1快照L是适宜的，如果对每两个相邻进程卩和q,恒有 心掩匸send爲一个快照的适宜性隐含了在暗指的形态构造中，进程q收到的来口进程P的 消息，一定是进程卩已经发送给进程g的消息定义1U・2瓦的一个割是一个集合厶，LyEy,满足：e g L 卜 A Y卩 e => g L 其中，耳表示所有事件的集合定义10・3耳的一个一致割是一个集合厶，LyE、,,满足：e w L N d Y e n d w L具中，瓦表示所有事件的集合定义10. 4快照S*在计算C中是有意义的，如果存在一个执行序列EqC, 满足/是E的一个形态其中，C是分布式系统的计算，它由进程集合P组成。
定理2（三个概念的等价性定理）令足…个快照，厶是厂所隐含的割，则卜列三个命题是等价的：（1） S*是适宜的；（2） 厶是一致割；（3） S是有意义的证明：见教材P211页2. 两个快照算法下面，我们介绍两个快照算法1） Chandy-Lamport 快照算法（见 P213） 具体算法（略）引理10.6如果至少有一个进程开始执行算法，那么，在有限时间内，所有进程将取得局部快照证明：因为每个进程取得快照和发送消息＜mkr＞至多一次，快照算法的活动 必然会在有限时间内停止如果p是那时已经取得快照的一个进程，且g是” 的邻居，那么，根拥算法，q也将取得快照这是由丁基于弱公平性假设，〃发 送给g的vmkr＞消息，在q收到Z后，如果q尚未取得快照，那么算法将导致它 马上取快照因为至少有一个进程对算法进行初始化，则至少有一个进程已经取得快照，而网络的连通性蕴涵着所有进程都将取得快照 口如果算法由任意非空进程集合初始化，它能否正确工作？定理10.7在至少有一个进程初始化算法Z后，Chandy-Lamport算法在有限时间内计算有意义的快照证明：由前述引理，算法在有限时间内将取得快照下而证明算法取得的快 照是有意义的，即在快照后事件中接收的是快照后消息。
设血是进程p发送给 进程q的快照后消息，在发送加Z前，卩取得了局部快照，并把消息＜mkr＞发送 给它的所有邻居，包括进程"因为通道是IFI0（先进先出）的，q必然在接收加 Z前接到这条消息＜mkr＞0按照算法，q 一旦接收到这条消息＜mkr＞,就取它的 快照因此，m的接收只能是快照后事件 口算法的复杂性如何?比较简单，我们把复杂性分析留给大家2） Lai-Yang 算法Lai-Yang的算法不依赖丁通道的IFIO（先进先出）性质，直接见P214定理10.8 Lai-Yang算法仅计算有意义的快照证明：考虑由算法计算获得的一个快照设m=
Toylor已经证明，只耍通道不是IFI0（先进先出）的，并且不能使用捎带消 息，快照问题的解决方法一定会受到抑制，即暂时挂起基本计算在有关通信的 假设下，对不同抑制类羽•的分类和对必须的抑制的特征藐视研究，可在相关文献 中找到3. 使用快照算法和取快照的时机（1）计算通道状态到冃前为止，我们都是假设每个进程的状态包含了进程的通信历史，因此， 可以从邻居进程的状态计算出快照中通道的状态但是，这样做，开销太大，我 们不可能把进程发送和接收的所有消息都明确地存储起来那么，怎样才能有效 地构造通道的状态呢？%1 简化有关信息这取决丁快照的冃的，并不是网络上形态中所有的变量值都是有用的，可以 只存储有限数量的相关信息即可；%1 明确构造通道的状态借助下列引理，可以明确地构造通道状态引理1（）・9在适宜的快照中,sen\rcw_q等于进程”在快照前事件中所 发送（给Q）的和q在快照后事件中所接收（来自P）的消息集合证明：一方面，容易证明，一条属^send^Xrcvd^中的消息加，在快照前 事件中被发送和在快照后事件中被接收，它们是取得快照时q尚未接收的那些消 息；另一方面，如果消息加在快照前发送和在快照后被接收，那么，根据定义, 它将被包含在send爲中,但不在rcvd\q中,因此,它是在send*pq \ rcvd\q中。
□显然，由引理10.9,只耍记录所有快照后事件中接收的快照前消息，进程q 就可以构造通道pq的状态由丁•所有这些消息是在q取得它的快照Z后才被接 收，所以，q在记录它的状态（局部快照）Z后开始记录这些消息即可，并且所有 快照前消息到达Z后，就停止记录再往后到达的消息都是快照后消息有了这样的分析，对丁上述两种快照算法，就不难构造通道状态了2）取快照的时机本章介绍的快照算法所构造的快照是有意义的除此之外，我们希望快照是 最近的，即获得的快照信息不是陈旧的我们可以将快照与分布式算法执行中出 现的形态联系起来考虑问题在算法的一次执行中，所计算的“快照”位丁•记录 开始时的初始形态和记录结束时的形态Z间，正如下列定理所描述的定理1U.1U令F是一次执行，E是F隐含的事件序列，S*是在E中取得的 适宜的快照，/是执行中蕴涵的系统形态设儿是第一个进程记录了它的局部 状态时达到的形态，乂设儿是最后一个进程记录了它的局部状态时到达的形态, 那么，仁2丫 2讥O证明：我们强调定理10.5的证明中使用的证明方法首先按照半件在E中 发生的次序来枚举E中的快照前事件，然后按照它们在E中出现的次序枚举E 中的快照后事件，来构造事件序列f o这个枚举与E的因果序关系是一致的， 因此，它定义了算法的一次执行F。
F按照这种次序包含形态人，人，这表明了我们所需耍的结呆显然, F包含儿，因为E中人Z前的所有事件都是快照前事件，故.f正好可以以相同的 次序从这些事件开始（/的前面一段与E的前面一段相同）尸包含乙，是因为执 行尸中的排在人Z前的事件集合包含了所有的快照前事件，故/中可以从这些快 照前事件开始（尽管可能以不同的次序），最后算法到达儿形态因为/与E的 因果序关系一・致，所以，根据定理2.21, F包含儿3）稳定性质的检测 %1 终止性%1 死锁%1 令牌丢失%1 无用信息%1 其它其它内容略4. 应用：死锁检测（略）如对操作系统的一个应用（略）OS=(C,->,/), T CXC y — 5 E = (/0, /p /() G Ii$0, 中,* E = (/0,兀，/，•••)Y^5(7 = Yv …，"=〃)0
