19助教部分算法问题解答-中科大研究生算法设计与分析期末复习全攻略.doc

1.

(1)由Lemma3.1可得。(同步匿名非均匀)

假设R是大小为n1的环（非均匀），A是其上的一个匿名算法，它选中某处理器为leader。因为环是同步的且只有一种初始配置，故在R上A只有唯一的合法执行。

Lemma3.1：在环R上算法A的容许执行里，对于每轮k，所有处理器的状态在第k轮结束时是相同的。Note：每个处理器同时宣布自己是Leader。

(2)

n个节点每个节点随机产生一个(1-n)的随机数作为自己的id，然后将它发送，

若绕场一周后回到了该节点，该节点就用那个id;

否则重新产生随机数，直到绕场一周回到该点；

对于每个节点若收到的msg中的id和自己产生的id一样就没收