3.3 基本算法

第一个解法相当显而易见，我们称其为LCR算法，以表彰Le Lann、Chang和Roberts，这个算法正是取自他们的论文。这个算法只使用单向通信，并且不依赖于是否知道环的规模。只有领导者才会执行输出决定。算法只需要对UID使用比较操作。以下是LCR算法的非形式化描述。

LCR算法（非形式化）：

每个进程都绕环发送自己的UID。当一个进程接收到一个UID时，就把它和自己的UID相比较。如果这个UID比自己的UID大，就继续传递这个UID；如果这个UID比自己的UID小，就丢弃UID；如果和自己的UID大小相同，就宣称自己是领导者。

在这个算法中，拥有最大UID的进程是唯一的领导者。为了证明这个直觉是正确的，我们将按第2章的模型来给出一个更加详细的算法描述。

LCR算法（形式化）：

字母表M是UID的集合。

对于每个i，states_i中的状态由以下部分组成：

u，一个UID，初值等于i的UID；

send，一个UID或者null，初值等于i的UID；

status，从{unknown,leader}中取值，初值为unknown。

开始状态start_i的集合由给定的初始化中定义的单个状态组成。

对于每个i，消息生成函数msgs_i按如下定义：

事实上，进程i会使用一个和进程i+1相关的名字，如“顺时针邻接节点”，为简便起见，我们写成i+1。回忆在第2章中，我们用值null作为一个占位符，表示消息不存在。所以，如果send的值为null的话，那么这个msgs_i函数实际上并没有发送任何消息。

对于每个i来说，状态转移函数trans_i用下面的伪码定义：

这个转移函数的第一行清除了以前的消息传递（如果有的话）对状态产生的影响。其余行完成了以下工作——决定是继续传递还是丢弃输入的UID，或者接受它，使自己成为领导。

算法的描述应当使用可读性好的程序语言，但是注意它可以直接翻译成在第2章的模型中的进程状态机。在这样的翻译中，每个进程状态由所有变量的值组成，而且状态转移可以根据变量的变化来描述。注意，作为单独一轮中的处理部分，整个trans_i函数的代码不可分割地执行。

我们怎样才能形式化地证明这个算法是正确的呢？正确性的含义是恰好有一个进程最终产生“领导者”输出。用i_max表示UID最大的进程，用u_max表示它的UID。需要证明：（1）进程i_max在第n轮结束时输出“领导者”；（2）没有其他进程输出“领导者”。我们分别在引理3.2和3.3中证明这两点。

在书中的很多地方，我们给状态分量加了下标i来表示这个分量是属于进程i的。例如：我们用符号u_i来表示进程i的状态分量u的值。但是一般我们会在编写代码的时候忽略这些下标。

引理3.2 进程i_max在第n轮结束时输出“领导者”。

证明 注意到u_max是初始化时变量u_imax的初始值，即变量u在进程i_max处的值。同时注意到变量u的值从不（被代码）改变，（根据假设）它们都是各不相同的，而且（由i_max的定义）i_max具有u的最大值。从代码看，已经足够来说明以下的不变式断言：

断言3.3.1 在n轮以后，status_imax=leader。

通常我们对轮数做归纳来证明这样的不变式。然而，为此我们需要一个预备不变式来说明少数几轮之后的情况。我们加入以下断言：

断言3.3.2 对0≤r≤n-1，在r轮之后，send_imax+r=u_max。

（回想一下，加法是模n加法。）这个断言说明send组件的最大值出现在环中与i_max距离为r的位置。

对r做归纳就可以很简单地证明断言3.3.2。当r=0时，初始化表明在0轮后，send_imax=u_max成立，得证。归纳步基于这样的事实：除i_max之外的每个节点接受最大值并把它放到send分量中，因为u_max大于其他所有的值。

在证明了断言3.3.2后，我们用它的特殊情况r=n-1和对单一轮中情况的讨论来说明断言3.3.1。这里的关键在于进程i_max把u_max作为设置自己为领导者的一个信号。

引理3.3 除进程i_max之外没有其他进程输出“领导者”。

证明 这只要证明其他进程总有status=unknown就足够了，有助于声明一个更强的不变式。如果i和j是环中任意两个进程，而且i≠j，则定义[i,j)为下标集{i,i+1,… ,j-1}，其中加法是模n加法。也就是说，[i,j)是一个进程集合，它包含从i开始沿顺时针方向直到j的逆时针邻接节点的进程。以下的不变式表明，没有UID v能够到达处于i_max与v的初始位置i之间任一位置的send变量：

断言3.3.3 对于任意的r和任意的i,j，在r轮之后，如果i≠i_max且j∈[i_max,i)，那么send_j≠u_i。

同样，使用归纳法来证明以上断言也是很容易的。证明中用到的关键事实在于一个非最大值不会通过i_max。这是因为i_max把输入的值和u_max比较，而u_max比其他任何UID都要大。

最后，断言3.3.3可以用于说明只有进程i_max可以在消息中接收自己的UID，所以只有进程i_max可以输出“领导者”。

引理3.2和引理3.3一起说明了以下的结论：

定理3.4 LCR算法解决了领导者选举问题。

停止和“非领导者”输出 如上所述，从所有进程都达到一个停止状态这个意义上讲，LCR算法永远都无法完成其工作。可以像2.1节中描述的那样扩充每个进程，使它们都包括停止状态。然后就可以修改算法，让选出的领导者在网络中发送一条特殊的报告消息。任何收到这个报告消息的进程都可以在传递该消息之后停止。这样的策略不仅可以允许进程停止，还可以让不是领导者的进程输出“非领导者”。更进一步，如果在消息上附上领导者进程的下标，那么这个策略可以让所有参与的进程都输出领导者的身份。注意，让每个不是领导者的进程在看到一个UID比自己大的进程时立即输出“非领导者”是可能的，但是这并不能告知非领导者节点何时停止。

一般说来，停止是一个分布式算法应满足的重要属性，但并不都像本例一样容易做到。复杂度分析 直到宣布一个领导者为止，基本LCR算法的时间复杂度是n轮，而通信复杂度在最坏的情况下是O(n2)。在带停止的算法版本中，时间复杂度是2n，但是通信复杂度还是O(n2)。停止和“非领导者”声明所需的额外时间是n轮，通信所需的额外消息是n个。变形 以上两部分描述和分析了一个基本的算法变形，即从只有领导者进程产生输出且没有进程停止的任意一种领导者选举算法，到一个领导者进程和非领导者进程都有输出并且所有进程都停止的算法。获取额外输出和停止的额外开销就是n轮和n个消息。对于其他任意的假设组合，这个变形都成立。

可变的开始时间 注意，在具有可变的开始时间的同步网络模型中，LCR算法无须改变。参看2.1节中关于这种模型的描述。

打破对称性 在一个环中选举领导者这个问题，其关键的难点是打破对称性。在分布式系统中需要解决许多其他问题，包括资源分配问题（见第10章、第11章和第20章）和一致性问题（见第5～7章、第12章、第21章和第25章），打破对称性也是其中一个重要部分。