3.9 习题

3.1 对LCR算法的正确性给出详细的归纳证明。

3.2 对LCR算法，

a）给出一个发送消息数为Ω(n2)的UID赋值方案。

b）给出一个发送消息数为O(n)的UID赋值方案。

c）证明发送消息数的平均数为O(nlogn)，其中对于环上所有可能的进程排序，该平均数都有效，假设所有可能的进程排序的概率相等。

3.3 修改LCR算法，使得所有的非领导者进程输出“非领导者”，并且最终停止所有的进程。用描述LCR算法的相同代码形式描述修改后的算法。

3.4 证明LCR算法在允许可变开始时间的同步模型中仍然适用（可能需要对代码稍做修改）。

3.5 详细证明HS领导者选举算法的正确性，利用LCR算法中用到的不变式断言。

3.6 证明HS算法在允许可变开始时间的同步模型中仍然适用（可能需要对代码稍做修改）。

3.7 假设对HS领导者选举算法做了修改，使用k的连续次幂，而不是2的幂，作为路径长度（k＞2）。用类似于书中分析原始的HS算法的方法，分析新算法的时间复杂度和通信复杂度，并将结果与原算法进行比较。

3.8 修改HS算法，使进程只向一个方向发送令牌。

a）证明这样对书中算法最直接的修改不会产生O(nlogn)的通信复杂度。通信复杂度的上限是多少？

b）在算法中稍微增加一些技巧，使其保证O(nlogn)的复杂度限制。

3.9 设计一个单向的领导者选举算法，使其可在大小未知的环中工作，最坏情况下的消息数为O(nlogn)。算法只对UID进行比较操作。

3.10 给出描述时间片领导者选举算法的状态机代码。

3.11 描述一个时间片算法的变形，它在每一阶段允许k个而不是1个UID在环中传递，通过额外的消息开销来节约时间。证明算法的正确性，并分析其复杂度。

3.12 给出描述变速领导者选举算法的状态机代码。

3.13 证明未修改的变速算法在进程唤醒时间不同的情况下，不一定有O(n)的通信复杂度。

3.14 证明在大小为n的环中，在最坏情况下，选举领导者所需轮数的最佳下限。请准确描述你的假设。

3.15 直观地表示出n=16的位反转环。

3.16 证明对任意的k∈N+，大小为n=2k的位反转环是1/2对称环。

3.17 对某一c＞0，设计一个非2的幂的c对称环。

3.18 考虑大小为n的同步环中的领导者选举问题，其中所有的进程都知道n，但进程没有UID。设计一个随机化领导者选举算法，也就是说，算法中的进程除了遵循确定的代码外，可以做出随机的选择。请准确描述算法满足的属性。例如，它能否绝对保证选出一个唯一的领导者，还是有失败的可能？算法期望的时间复杂度和通信复杂度是多少？

3.19 考虑一个双向的同步环，大小n未知，其中的进程具备UID。给出一个基于比较的算法所要求的消息数的上限和下限，在这个算法中，所有的进程都计算n模2。

---

[1] 可以忽略平方根的下限条件——这仅是个技术问题。

[2] 注意，位反转环不需要平方根的下限条件。

[3] 这里有平方根下限的问题。

[4] 表达式Ω(nlogn)隐藏了一个与n无关的固定常数。