第4章 一般同步网络中的算法

在第3章中，我们给出了对简单同步网络——单向环和双向环——中的领导者选举问题的算法及其下限。在这一章中，我们要考虑在更大类同步网络中的更多问题。特别地，我们将在基于任意图和有向图的网络中，讨论领导者选举、广度优先搜索（BFS）、寻找最短路径、寻找最小生成树（MST）和寻找最大独立集（MIS）的算法。

当需要选举一个进程来负责整个网络的计算时，就出现了领导者选举问题。而广度优先搜索、寻找最短路径和最小生成树这些问题来源于构建适合于支持有效通信的结构这一需要。寻找最大独立集的问题源于网络资源分配的需要（在第15章的异步网络环境中，我们还会讨论这些问题）。

在这一章中，我们考虑一种任意的强连通网络有向图G=(V,E)，它有n个节点（有时我们只考虑所有边都是双向边的情况，即无向图的情况）。像通常的同步网络系统一样，我们假设进程仅仅通过图的有向边通信。为了给节点命名，给它们分配下标1,…,n，但是与环的下标不同，这些下标与图中节点位置并无特殊联系。进程并不知道自己的下标，也不知道邻接节点的下标，但是能够通过本地名字来指称邻接节点。我们假定，如果进程i的出向和入向邻接节点都为同一进程j，那么i知道这两个进程是相同的。