并行与分布式系统中的分布式最小生成树：GHS算法（Gallager-Humblet-Spira） 问题描述 在分布式系统中，假设有一个由多个节点（处理器）构成的连通无向图，每条边有一个权重。目标是通过节点间的消息传递，协作计算出图的最小生成树（MST）。GHS算法是解决这一问题的经典分布式算法，适用于异步通信模型，且保证每个节点最终知道自己在MST中的邻接边。 解题过程 1. 核心思想 GHS算法基于 分治策略 ：将图中的节点划分为多个子树（称为“片段”），每个片段内部已形成MST，逐步合并片段，直到所有节点属于同一个片段。合并时，每个片段找到连接自身与其他片段的 最小权重出边（MOE） ，通过MOE合并片段，确保全局MST的正确性（遵循Kruskal算法的贪心原则）。 2. 关键概念 片段（Fragment） ：一棵已形成的MST子树，有一个唯一的标识符（通常为片段中最小节点ID或最小边权重）。 最小权重出边（MOE） ：连接当前片段与外部节点的边中权重最小的边。 层级（Level） ：片段的合并优先级。初始时每个节点是层级为0的片段；合并时，层级相同的片段可合并，新片段层级+1。 3. 算法步骤详解 初始化阶段 ： 每个节点初始化为独立的片段（层级=0），片段ID为自身节点ID。 每个节点开始寻找自己的MOE（即所有邻接边中权重最小的边）。 片段合并循环 ： 寻找MOE ： 每个片段通过内部广播（沿当前片段的MST边）收集所有候选出边（连接外部节点的边）。 比较候选边权重，确定片段的MOE及其连接的外部片段。 合并协商 ： 当前片段通过MOE向外部片段发送合并请求（包含自身层级和片段ID）。 若接收方片段层级相同，则同意合并，双方同步层级和新的片段ID（取两个片段ID的最小值）。 若接收方层级更高，则拒绝合并，当前片段需等待直至层级提升。 片段合并与层级更新 ： 同意合并后，MOE被加入MST，两个片段合并为一个新片段。 新片段的层级为原层级+1，片段ID更新为合并双方ID的最小值。 新片段重新开始寻找MOE，重复上述过程。 终止条件 ： 当所有节点属于同一个片段（层级相同且无法找到MOE）时，算法终止。 4. 消息类型与通信 Search_ MOE ：在片段内广播，收集候选出边。 Test ：询问对端节点是否属于同一片段（用于判断边是否为出边）。 Merge_ Request ：请求合并片段。 Accept/Reject ：回应合并请求。 Level_ Update ：通知片段内节点层级变化。 5. 示例说明 假设有4个节点A、B、C、D（ID为A<B<C <D），边权重为AB=2、AC=3、BD=1、CD=4： 初始时，每个节点为层级0的片段。 A找到MOE为AB（权重2），B找到MOE为BD（权重1）。片段A和B通过AB合并（新片段ID=A，层级=1）。 新片段A-B找到MOE为BD（连接D），与片段D合并（新片段ID=A，层级=2）。 片段A-B-D找到MOE为AC（连接C），与片段C合并（全局MST形成）。 关键点 正确性 ：MOE合并保证每次加入的边是全局最小权重的有效边（类似Kruskal）。 复杂度 ：消息复杂度为O(E + N log N)，其中E为边数，N为节点数。 容错 ：算法假设异步通信，但需避免死锁（通过层级机制保证进度）。 通过以上步骤，GHS算法以分布式方式逐步构建MST，每个节点仅与邻居通信，无需全局视图。