3.5.2 变速算法

时间片算法表明，在进程知道环的规模为n的那些环中，消息数为O(n)就足够了。但是如果n是未知的呢？在这种情况下，同样存在消息数为O(n)的算法，我们称之变速算法。这个算法只使用单向通信。

但是，变速算法的时间复杂度甚至比时间片算法还要差，为。当然，没有人会在实际中运用这样的算法。我们称变速算法为一个反例算法。一个反例算法的主要目的是说明某个推想的不可能性结果是错误的。这种算法本身并无意义——不实用，从数学的观点来看也不精确。但是，它可以说明一个不可能性结果不成立。

下面就是这个算法的描述。

变速算法：

每个进程i创建一个令牌，令牌带着发起进程i的UID u_i在网络中流动。不同令牌的流动速度是不一样的。一个带着UID v的令牌的速度为每2v轮传递一条消息，也就是说每个进程在接收这个令牌以后需要等到2v轮之后才能将它发出。

同时，每个进程都会保存自己见到的最小UID，并丢弃任何包含比最小UID更大的UID的令牌。

如果令牌返回到创建进程，那么这个进程就被选为领导者。

和时间片算法类似，变速算法保证了拥有最小UID的进程会被选出。

复杂度分析 变速算法保证了最小UID u_min的令牌会流过整个网络，而次小的令牌会流过大约一半的网络，第三小的令牌流过大约四分之一的网络，一般来说，按从小到大排序UID，排在第k位的令牌会流过的路程。直到领导者被选出为止，最小UID的令牌使用的消息数比所有其他令牌用到的消息数的和还要多。因为u_min正好使用n个消息，所以总的消息数小于2n。

但是，注意当u_min流过了整个网络的时候，所有的节点都会知道这个值，并会拒绝发出其他令牌。在这个算法中，2n是发送消息数的上限。

如上所提到的，时间复杂度是，因为每个节点都会将UID为u_min的令牌延迟个时间单位。

可变的开始时间 不像LCR和HS算法，变速算法不能像具有可变开始时间的同步网络模型中的那样使用，但是可以通过修改算法来实现：

改进的变速算法：

如果一个进程在接收到任一普通（非空）消息之前（必须正好在提前一轮中）接收到一条唤醒消息，则定义它为开始者（starter）。

每个开始者i发出一个带着自己的UID u_i的令牌在网络中流动；非开始者不能创建令牌。开始时，令牌走得很“快”，每轮传递一次，它通过所有被令牌的到来而唤醒的非开始者进程，直到首次到达一个开始者（可以为不同的开始者，也可以为进程i自己）。当令牌到达开始者以后还会继续传递，但是速度减慢到每轮传递一次。

同时，每个进程都保存所见到的最小UID的开始者，并且丢弃任何比这个UID大的进程的令牌。如果令牌回到原始进程，那么该进程会被选为领导者。

这个改进的变速算法保证了具有最小UID的开始者进程能够被选出。用i_min-start来表示这个进程。

复杂度分析 我们分三类来对消息计数。

1）与开始时令牌的快速传递过程相关的消息，共有n条。

2）直到i_min-start的令牌首次到达一个开始者为止，与令牌的慢速传递过程相关的消息。从第一个进程被唤醒时开始，这至多需要n轮。在这段时间中，一个带着UID为v的令牌可能最多用到条消息，一共最多条消息。

3）在i_min-start的令牌首次到达开始者之后，与令牌的慢速传递过程相关的消息。这里的分析和基本变速算法差不多。在获胜令牌走完整个路程时，按从小到大排序UID，排在第k位的令牌只走了至多的路程。所以，到选出领导者时，发送的总消息少于2n。但是在获胜令牌走完整个路程时，所有的节点都会知道它的值，并会拒绝发出其他令牌，所以2n是消息数的上限。总的通信复杂度最大为4n。

时间复杂度为。