3.1 问题

我们假设网络有向图G是一个由编号为1～n的n个节点构成的顺时针方向的环（见图3-1）。我们经常使用模n计数，所以0是进程n的另一个名字，而n+1是进程1的另一个名字，依此类推。与G的节点相关的进程并不知道自己的编号（即下标），也不知道它们邻接节点的编号。我们假设消息生成函数和迁移函数都根据本地的、相对于邻接节点的名字来定义。然而，每个进程都必须能够将它的顺时针邻接节点和逆时针邻接节点区分开来。要求是：最后应该恰好只有一个进程输出这个决定，即它就是领导者，通过将其状态中的特定部分改为值“领导者”。定义问题：

图3-1 进程环

1）可能要求所有非领导者的进程最终把其状态部分的值改为“非领导”，表示自己不是领导者；

2）环有可能是单向的也有可能是双向的。如果是单向的话，每条边都从一个进程指向其顺时针的邻接节点，也就是说，消息只能依照顺时针的方向发送；

3）在环中，对于进程来说，节点的个数可能是已知的，也可能是未知的。如果是已知的，意味着进程只需要在规模为n的环中正确工作，因此它们可以在程序中利用值n。如果是未知的，意味着这个进程必须能在节点数不同的环中工作，此时不能使用有关环规模的信息；

4）进程可以是相同的，也可以用进程开始时的唯一标识符（UID）来区分，UID取值于某个大的全序标识符空间，如正整数集N+。我们假设在环中每个进程的UID都是不一样的，但是并不限定哪些UID实际出现在环中（例如：它们并不一定是连续的整数）。这些标识符可以只限于接受某些特定操作，如比较操作，又如它们允许不受限制的操作。