2.1 同步网络系统

同步网络系统由一组位于有向网络图节点上的计算元素组成。在第1章，我们称这些计算元素为“处理器”，这说明它们是硬件。但是，把它们看成逻辑软件“进程”往往是很有用的，这些进程在实际的硬件处理器上运行（而不是等同于处理器）。我们给出的结论适用于上述两种情况。在本书中，自现在开始，我们约定称计算元素为“进程”。

为了形式化地定义同步网络系统，我们从有向图G开始，G=(V,E)。我们用n表示网络有向图中的节点个数，即|V|。对于G中的任意节点i，我们用out-nbrs_i[1]表示i的“出向邻接节点”，也就是说，在G中存在i到这些节点的有向边；同样，in-nbrs_i表示“入向邻接节点”，即在G中存在这些节点到i的有向边。我们用distance(i,j)表示在G中从i到j的最短有向路径的长度；如果不存在这样一条路径，则设distance(i,j)=∞。我们定义diam，即直径，为所有(i,j)的distance(i,j)的最大值。我们假设M是一个固定的消息集合，null是一个占位符，表示没有消息。

对应每个i∈V，存在一个进程，它在形式上由下列几部分组成：

● states_i，一组状态的集合（不一定是有限集）；

● start_i,states_i的非空子集，称为开始状态集或初始状态集；

● msgs_i，一个消息生成函数，从states_i×out-nbrs_i映射到M∪{null}；

● trans_i，一个状态迁移函数，从状态集states_i和M∪{null}中元素组成的向量（以in-nbrs_i为下标）映射到states_i。

可见，每个进程都有一个状态集合，其中又分出一个子集——开始状态集合。状态集不一定是有限集，这一点很重要，因为这样我们可以表示某些系统，其中包含像计数器这样的无界数据结构。对于每个状态和出向邻接节点，消息生成函数定义了从给定状态开始，进程i向指定的邻接节点发出的消息。状态迁移函数则定义了针对每个状态和所有来自入向邻接节点的消息的集合，进程i所要迁移到的状态。

对应于G中的每一条边（i,j），存在一条通道，也称为链路，它是在任意时刻最多持有M中一条消息的一个场所。

整个系统的运行以所有进程处于任意开始状态和所有通道都为空开始。之后，所有的进程在每个时间步重复执行下列步骤：

1）对当前状态应用消息生成函数，生成所有向出向邻接节点发送的消息，把这些消息放在相应的通道上；

2）对当前状态和入向消息应用状态迁移函数，获得新的状态，删除通道上的所有消息。

上述两步的组合称为一轮（round）。注意，进程往往需要通过计算来确定消息生成函数和状态迁移函数的值，通常我们不对计算量加以限制。同时，我们讨论的模型是确定性模型，也就是说消息生成函数和状态迁移函数是单值函数。因此，给出初始状态的一个特定集合后，计算将以唯一的方式展开。

停止 到目前为止，我们还没有对进程的停止做任何规定。然而，分辨出哪些状态是停止状态并指出从这些状态开始不会有进一步的活动是很容易的。停止状态意味着不会有任何消息生成，同时唯一的状态迁移是自循环。注意，停止状态在我们的系统中所扮演的角色与在传统的有限状态自动机中是不同的。在有限状态自动机中，停止状态是作为接受状态存在的，用来决定哪些字符串属于该自动机所计算的语言。而在这里，它只是用来停止进程；进程所计算的内容必须取决于其他的约定。接受状态这种概念往往不适用于分布式算法。

变量开始时间 有时，我们需要考虑在同步系统中进程有可能从不同的轮开始执行。我们通过扩展网络图来表示这种情况，使网络图中包括一个特殊的环境节点，该节点与所有的普通节点相连。相关的环境进程的工作是向其他所有节点发送特殊的唤醒消息。每个其他进程的所有初始状态都要求是休眠的，即这些状态不会生成任何消息，并且只有当它从环境进程收到唤醒消息或者从其他进程收到非空消息时，它才迁移到新的状态。这样，一个进程可以被外界的唤醒消息直接唤醒，也可以被其他已经唤醒的进程的非空消息唤醒。

无向图 有时，我们需要考虑底层的网络图是无向图的情况。把无向图看作具有双向边的有向图，从而使用我们已经针对有向图定义的模型来表示这种情况。在这种情况中，用nbrs_i来代表i的邻接节点。