3.5.1 时间片算法

第一个算法用到了一个很强的假设：环的大小n对所有进程来说是已知的，但只假定是单向通信。我们所说的时间片算法就在这样的设定下工作。它选择具有最小UID的进程。

注意，这个算法比LCR和HS算法更深入地利用了同步性。也就是说，它在某些轮处利用了非到达消息（即到来的是null消息）来传递信息。

时间片算法：

在阶段1,2,…中进行计算，每一个阶段都由n个连续的轮组成。每个阶段都有一个携带着特殊UID的令牌一直在环中流转。更特别地，在包含轮(v-1)n+1,…,vn的阶段v中，只有带着UID v的令牌才被允许流转。

如果存在UID为v的进程i，且在(v-1)×n+1轮到达之前进程i没有收到任何非空消息，那么进程i会把自己选举为领导者，并沿着环发送一个包含其UID的令牌。当这个令牌在传递的时候，所有其他进程都接收到它，这样它们就不会选举自己为领导者或在以后的阶段中创建令牌。

在这个算法中，最小的UID u_min最终会环绕整个路径，使得它的原始进程被选为领导者。在第(u_min-1)n+1轮之前，不会有任何消息发送，并且在u_min×n轮之后，也不会发送任何消息。总共发送的消息的数量是n。如果想选出具有最大UID而不是最小UID的进程，那么我们可以让具有最小UID的进程在被发现后发送一个特殊的消息来确定最大UID的进程。通信复杂度还是O(n)。

时间片算法的好处就是消息的总数是n个。但不幸的是，时间复杂度大约是n×u_min，这在固定规模的环中也是一个无界数。这个时间复杂度限制了这个算法的实际应用。它只能用于那些小的环网络中，其中的UID都是很小的正整数。