●●● ●●●● ●●●●● ●●●● 33选举算法 ●●●0● ●●●0 ●许多分布式算法需要一个进程充当协调者、发 起者、排序者或者其他特定的角色 ●例如:集中式互斥算法中的协调者进程 ●通常,选择哪个进程充当协调者并不重要,重 要的是要有进程负责,并且需要所有进程的 致认可。 陈香兰@2007.3 分布式系统同步
陈香兰@2007.3.21 分布式系统同步（续） 2 3.3 选举算法 ⚫ 许多分布式算法需要一个进程充当协调者、发 起者、排序者或者其他特定的角色 ⚫ 例如：集中式互斥算法中的协调者进程 ⚫ 通常，选择哪个进程充当协调者并不重要，重 要的是要有进程负责,并且需要所有进程的一 致认可
●●● ●●●● ●●●●● ●●●● 最大进程号 ●●●0● ●●●0 ●如果所有进程的地位都相同,没有特性上的区 别,就无法选择其中一个为特殊进程; ●假设每个进程都有一个特殊的号,通常选举算 法总是找拥有最大号的进程,将它指定为协调 者,不同的选举算法在选举时采用不同的方法 陈香兰@2007.3 分布式系统同步
陈香兰@2007.3.21 分布式系统同步（续） 3 最大进程号 ⚫ 如果所有进程的地位都相同，没有特性上的区 别，就无法选择其中一个为特殊进程； ⚫ 假设每个进程都有一个特殊的号，通常选举算 法总是找拥有最大号的进程，将它指定为协调 者，不同的选举算法在选举时采用不同的方法
●●● ●●●● ●●●●● ●●● 选举的目的 ●●●0● ●●●0 ●我们假设每个进程都知道所有其他进程的进程 号,但不知道目前哪些进程在工作,哪些进程 不在工作; ●选举算法的目的是在选举开始后,确保在所有 进程都同意的基础上选出协调者 陈香兰@2007.3 分布式系统同步
陈香兰@2007.3.21 分布式系统同步（续） 4 选举的目的 ⚫ 我们假设每个进程都知道所有其他进程的进程 号，但不知道目前哪些进程在工作，哪些进程 不在工作； ⚫ 选举算法的目的是在选举开始后，确保在所有 进程都同意的基础上选出协调者
●●● ●●●● ●●●●● ●●●● 两个选举算法 ●●●0● ●●●0 欺负(Buy)算法 环算法 陈香兰@2007.3 分布式系统同步
陈香兰@2007.3.21 分布式系统同步（续） 5 两个选举算法 ⚫ 欺负（Bully）算法 ⚫ 环算法
●●● ●●●● ●●●●● ●●●● 331欺负(Buly)算法 ●●●0● ●●●0 Buy算法由 Garcia-Mona在1982年提出 当一个进程P发现协调者不再响应请求时, 它就发起选举。进程P负责选举如下 1.P向所有进程号比它大的进程发送选举 ( ELECT|ON)消息; 2.若无人响应,P获胜成为协调者; 3.若有进程号比它大的进程响应,响应者接管,P 的工作完成。 由于总是进程号最大的进程获胜,故该算法 命名为欺负算法 陈香兰@2007.3 分布式系统同步
陈香兰@2007.3.21 分布式系统同步（续） 6 3.3.1 欺负（Bully）算法 ⚫ Bully算法由Garcia-Molina在1982年提出 ⚫ 当一个进程P发现协调者不再响应请求时， 它就发起选举。进程P负责选举如下： 1. P向所有进程号比它大的进程发送选举 （ELECTION）消息； 2. 若无人响应，P获胜成为协调者； 3. 若有进程号比它大的进程响应，响应者接管，P 的工作完成。 ⚫ 由于总是进程号最大的进程获胜，故该算法 命名为欺负算法