3.4 通信复杂度为O (nlogn）的算法
虽然LCR算法的时间复杂度比较低，但是用到的消息数目比较大，共有O(n2)。这看起来好像不是很重要，因为在任一时刻任一链路中的消息不会多于一个。但是，在第2章中，我们已经讨论了为什么消息条数是一个值得注意的应该越少越好的衡量标准，这是因为对于许多并发运行的分布式算法，其总的通信负载可能导致网络拥塞。在本节中，我们将要介绍一个算法，它把通信复杂度降为O(nlogn)。
第一个将最坏情况下的复杂度降到O(nlogn)的算法由Hirschberg和Sinclair提出，所以称这个算法为HS算法。我们再次假定只有领导者需要执行输出，尽管在3.3节结尾中提到的变形暗示着这个限制并不重要。另外，我们假设环的规模是未知的，但是现在允许双向通信。
就像LCR算法所做的那样，HS算法也选出具有最大UID的进程。每个进程，不是像LCR算法中那样把自己的UID在网络中一直传递下去，而是把它传到某个距离之外，然后反转回来，再回到原来的进程。它如此反复地逐步增大距离。HS算法的非形式化描述如下所述。
HS算法（非形式化）：
每个进程i在阶段0,1,2…中操作。在每个阶段l中，进程i向两个方向发出包含自己UID，即包含ui的“令牌”。这些令牌会前进2l的距离，然后回到自己原来的进程i（见图3-2）。如果两个方向的令牌都能够安全回来，那么进程i就会继续下一个阶段。但是，令牌可能不会安全返回。当一个ui的令牌在外出方向前进时，任何在ui前进路径上的进程j都会对自己的UID，即uj和ui进行比较。如果ui＜uj，那么进程j就会丢弃这个令牌；如果ui＞uj，它就会继续传递ui。如果ui=uj，则说明进程j在令牌反转之前就已经接收到自己的UID，所以进程j就会把自己选为领导者。
所有进程总是继续传递所有进入方向的令牌。
图3-2 HS算法中进程i处发起的连续令牌的轨迹
下面我们来更形式化地描述这个算法。这次，需要一些簿记（bookkeeping）以保证令牌能沿着正确的轨迹运动。例如：令牌会带上一个标志来表示它们到底是外出还是进入。同样，令牌也会带上跳跃计数（hop count）来记录它们在外出方向上必须走的距离；这允许进程计算出应在何时反转令牌的方向。一旦算法以这样的方式进行形式化，我们就可以给出类似于LCR算法中的正确性证明。
HS算法（形式化）：
消息字母表M是一个元素为三元组的集合，三元组包括一个UID、一个来自{out,in}的标志值和一个正整数“跳跃计数”。
对每一个进程i，状态statesi包括以下分量：
u,UID类型，初始值为进程i的UID
send+，包含M中的一个元素或null，初始值为由i的UID、out和1构成的三元组
send-，包含M中的一个元素或null，初始值为由i的UID、out和1构成的三元组
status,{unknown,leader}中的一个值，初始值为unknown
phase，一个非负整数，初始值为0
开始状态starti的集合包含给定的初始化定义的单个状态。
对每一个i，消息生成函数msgsi定义如下：
对每一个i，转移函数transi用下面的伪码定义：
像以前一样，前两行用来清除状态。接下来的两段代码用来处理外出方向的令牌：如果令牌的UID大于ui，则根据跳跃计数决定继续传递或者折回；如果ui到来，i就把自己选举为领导者。再下面的两段代码用来处理进入方向的令牌：它们只是简单地被继续传递（跳跃计数1用于进入的令牌）。如果进程i接收到了自己的两个返回令牌，那么它会进入下一个阶段。
复杂度分析 我们首先来分析通信复杂度。每个进程在阶段0发出一个令牌；令牌双向出去和返回，这总共需要4n条消息。对于l＞0，如果进程接收到了在l-1阶段的两个返回令牌，就会发送它在阶段l的令牌。如果在沿着环的两个方向且距离在2l-1以内它都没有被另一个“进程”击败，就出现这种情况。这就暗示着在任意一组2l-1+1个连续进程内，最多只有一个进程可以在阶段l发送令牌。因此在阶段l最多只有
个进程可以发送令牌。那么在阶段l发送的总的消息数就限于
这是因为阶段l的令牌能前进2l的距离。而因子4源于这样的事实：令牌同时被双向发送（顺时针和逆时针），而且每一个外出的令牌必须反转并返回。
在选举出领导者和所有通信都停止之前要执行的总的阶段数最多是
（包括阶段0），所以总的消息数最多是
，即O(nlogn)，其常数因子接近于8。
这个算法的时间复杂度仅为O(n)。因为对于每个阶段l的时间是2×2l=2l+1（因为令牌要出去并返回）。最后阶段需要的时间为n——这是一个未完成阶段，其中令牌只向外发送。倒数第二个阶段是
，它的时间复杂度至少和前面所有阶段的总和一样大，所以总的时间复杂度最多是2×2┌loogn┐。
如果n为2的幂，则总的时间复杂度最多为3n，否则是5n。其他的细节留为一道习题（习题3.6）。
可变的开始时间 HS算法在具有可变的开始时间的同步网络模型中不需修改。