●●● ●●●● ●●●●● ●●● ●●●0● ●●●0 ●进程6接管,向所有的运行进程发送 COORDINATOR 协调者消息 协调者 协调者 (e) 进程4收到消息,发现进程7已死,进程6是新协调者 进程4就可继续工作 这样,进程7的失效得到了处理 陈香兰@2007.3 分布式系统同步(续)
陈香兰@2007.3.21 分布式系统同步（续） 12 ⚫ 进程6接管，向所有的运行进程发送COORDINATOR 协调者消息 ⚫ 进程4收到消息，发现进程7已死，进程6是新协调者， 进程4就可继续工作。 ⚫ 这样，进程7的失效得到了处理
●●● ●●●● ●●●●● ●●● 332环算法 ●●●0● ●●●0 ●环算法(基于没有令牌的环) ●假设所有的进程是按物理或逻辑环排序的,每个进 程都知道谁是它的下邻居 个进程发现协调者不再起作用时,它就创建 个包含它自身进程号的选举消息发送给它的下邻居。 ●如果下邻居失效,消息将绕过它到达它的下邻居, 或者再下一个,直到找到一个运行进程。 每一个发送者都将自己的进程号加入到消息表中。 陈香兰@2007.3 分布式系统同步
陈香兰@2007.3.21 分布式系统同步（续） 13 3.3.2 环算法 ⚫ 环算法（基于没有令牌的环） ⚫ 假设所有的进程是按物理或逻辑环排序的，每个进 程都知道谁是它的下邻居。 ⚫ 当一个进程发现协调者不再起作用时，它就创建一 个包含它自身进程号的选举消息发送给它的下邻居。 ⚫ 如果下邻居失效，消息将绕过它到达它的下邻居， 或者再下一个，直到找到一个运行进程。 ⚫ 每一个发送者都将自己的进程号加入到消息表中
●●● ●●●● ●●●●● ●●●● ●●●0● ●●●0 ●最后,消息到达了始发者手中,始发者接收到包括 自己进程号的消息后,将消息的类型转化为协调者 消息,该消息将再一次绕环运行,向所有的进程通 知谁是协调者(在成员表中进程号最大的那个) 当消息循环一周后,被销毁,每个进程都恢复工作 陈香兰@2007.3 分布式系统同步
陈香兰@2007.3.21 分布式系统同步（续） 14 ⚫ 最后，消息到达了始发者手中，始发者接收到包括 自己进程号的消息后，将消息的类型转化为协调者 消息，该消息将再一次绕环运行，向所有的进程通 知谁是协调者（在成员表中进程号最大的那个）。 ⚫ 当消息循环一周后，被销毁，每个进程都恢复工作
●●● ●●●● ●●●●● ●●● 举例 ●●●0● ●●●0 ●进程2、5同时发现前任协调者进程7失效, 们各自建立一个选举消息沿环发送。 选举消总 以前的协 调者 没有应答 近举消 陈香兰@2007.3 分布式系统同步(续) 图312使用环的选举算法
陈香兰@2007.3.21 分布式系统同步（续） 15 举例 ⚫ 进程2、5同时发现前任协调者进程7失效，它 们各自建立一个选举消息沿环发送
●●● ●●●● ●●●●● ●●● ●●●0● ●●●0 ●最终,两条消息都将沿环运动,进程2和5分别 将它们转化成协调者消息,消息中有完全一样 的成员,相互顺序也相同,当两条消息再绕环 周后,均被销毁,有多余的消息循环没有坏 处,最多是浪费了一点带宽。 陈香兰@2007.3 分布式系统同步
陈香兰@2007.3.21 分布式系统同步（续） 16 ⚫ 最终，两条消息都将沿环运动，进程2和5分别 将它们转化成协调者消息，消息中有完全一样 的成员，相互顺序也相同，当两条消息再绕环 一周后，均被销毁，有多余的消息循环没有坏 处，最多是浪费了一点带宽