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

4.1 一般网络中的领导者选举

4.1.1 问题

  • ？？？。

4.1.2 简单的洪泛算法

  • 洪泛最大值算法选出具有最大UID的进程。

  • ``` states consists of components:

​


#### 4.1.3 降低通信复杂度

* 有一个简单的优化可以用来减少通信复杂度，进程可以只在它们初次知道max-uid的时候发送消息，而不是在每轮中都要发送，此算法叫优化洪泛最大值算法。

test ```

4.2.2基本的广度优先搜索算法

  • SynchBFS算法：在运行中的任一时刻，总有一个进程集合是被“标记的”，最初的时候是i0。进程i0在第一轮时向所有出向邻接节点发出一个搜索消息。在每一轮，如果一个未标记的进程接受到一个“搜索”消息，就标记它自己，并从传来的“搜索”消息的进程中选择一个作为父节点。在一个进程被标记之后的第一轮，它向所有的出向邻接节点发送“搜索”消息。降低通信复杂度，可以稍微减少消息数目：一个新标记的进程不需要再向传来“搜索”消息的进程发送消息。

  • BSF变形（子节点指针）：每一个进程不仅仅需要知道谁是它的父节点，还要知道哪些是它的子节点。在这种情况下，每个接受到“搜索”消息的进程就必须回复一个“父节点”或“父节点”消息，告诉消息的发送者，是否它已经被接受者选择为父节点。

4.3 最段路径

  • 最短路径：权最小的一条路径。每个有向边都有一个非负的实数值“权”相关联。

4.4 最小生成树

考虑在一个具有带权边的无向图网络中找到一颗最小（或最小权）的生成树（MST）。

  • 领导者选举，对于一个基于无向图的网络来说，一旦一个MST是已知的，那么给定UID，就很容易选举一个领导者，也就是说，从叶子节点开始沿着树的路径做聚播；每一个内部节点在向它的邻接节点发送消息前，等待其他所有邻接节点的消息。如果一个节点收到了它的所有邻接节点的消息，而自己没有发出任何消息，那么它是领导者。

results matching ""

    No results matching ""