数据库系统内幕

领导者选举

｜

183

•

c) 4 将新的领导者 2 通知给所有进程。

候选节点组 候选节点组 候选节点组普通节点组 普通节点组 普通节点组

a

）

b

）

c

）

图

10-3

：霸道算法的候选节点

/

普通节点修改版。先前的领导者（

6

）发生故障，进程

4

发起

新的选举

10.4

邀请算法

邀请算法

（invitation algorithm）允许进程“邀请”其他进程加入它们的组，而不是试图

超越它们的排名。这种算法

从定义上

就允许多个领导者存在，因为每个组都有自己的领

导者。

每个进程一开始都是一个新组的领导者，组内唯一的成员是这个进程本身。组领导者联

系不属于该组的对等进程，邀请其加入。如果对等进程本身是领导者，则合并两个组。

否则，被联系的进程会回复组领导者 ID，从而让两个组的领导者以较少的步骤建立联系

并合并两个组。

图 10-4 给出了邀请算法的执行步骤：

•

a) 开始时，有四个进程成为各有一名成员的组的领导者。1 邀请 2 加入它所在组，3

邀请 4 加入它所在组。

•

b) 2 加入进程 1 的组，4 加入进程 3 的组。1 作为第一组的领导者去联系另一组的

领导者 3。随后，该组剩余的成员（在本例中为 4）被通知关于新的组领导的信息。

•

c) 两个组被合并，并且 1 成为扩展后组的领导者。

因为组被合并了，是建议组合并的进程还是另一个进程成为新的领导者都无关紧要。为

了将合并组所需的消息数量保持在最低限度，较大组的领导者可以成为新组的领导者。

这样，只需要把领导者变更的消息通知给较小组的进程。