关于单向环Peterson改进选举算法的消息量计算问题

算法代码 #

tid := initial value
    do forever
         begin
             send(tid)         /* Compare to the left */
             receive(ntid)
             if ntid = initial value then announce elected
             if ntid > tid then goto relay
             send(tid)         /* Compare to the right */
             receive(ntid)
             if ntid = initial value then announce elected
             if ntid < tid then goto relay else tid := ntid                            
         end
    relay:
    do forever
         begin
             receive(ntid )
             if ntid = initial value then announce elected
             send(ntid )
         end

问题分析 #

给定n=4k个进程组成的单向环，进程ID排列为：1/4段递增、1/4段递减、1/4段递增、1/4段递减。最坏情况是全局最大ID位于递减段的起始位置，此时所有其他进程会尽可能多地发送竞争消息，直到进入中继状态，最终最大ID的消息绕环一周触发当选。

精确消息量计算 #

1. 竞争阶段消息量 #

将环分为4个长度为k的段，分别记为递增段S1、递减段S2、递增段S3、递减段S4，其中S2的第一个进程持有全局最大ID：

• 递增段S1和S3：每个段内的进程会不断更新自己的tid为右侧更大的ID，直到拿到更大的外部ID。每个段的消息量为：
  $$\sum_{i=1}^k 2i = k(k+1)$$
  两个递增段总消息量为：$2k(k+1)$
• 递减段S2和S4：每个段的第一个进程会完成完整的左右发送（2条消息），其余k-1个进程仅向左发送1条消息后进入中继。每个段的消息量为：$2 + (k-1) = k+1$
  两个递减段总消息量为：$2(k+1)$

竞争阶段总消息量：
$$2k(k+1) + 2(k+1) = 2(k+1)^2$$

2. 中继阶段消息量 #

当所有进程进入中继状态后，全局最大ID的消息需要绕环一周，每个进程转发一次该消息，共产生n=4k条转发消息。

3. 总消息量 #

将竞争阶段和中继阶段的消息量相加，代入n=4k（即$k=\frac{n}{4}$）：
$$总消息量 = 2(k+1)^2 + 4k$$
展开并替换k为n/4：
$$总消息量 = \frac{n^2}{8} + 2n + 2$$

该公式即为n为4的倍数时，最坏情况的精确消息发送量。

内容的提问来源于stack exchange，提问作者algorithm-cracker