算法与数据结构 分布式算法课程 第09章 基本异步网络算法 共71页.pdf

【课程大纲】 第01章 简介 共68页.pdf 第02章 分布式算法简介 共59页.pdf 第03章 集群领导选举 分布式锁 共83页.pdf 第04章 通用同步网络的集群领导选举 共69页.pdf 第05章同步网络中的基础计算 共76页.pdf 第06章 分布式一致性 共48页.pdf 第07章 Byzantine协议 共34页.pdf 第08章 异步系统模型 共47页.pdf 第09章 基本异步网络算法 共71页.pdf 第10章 同步化器 共39页.pdf 第11章 异步共享内存系统 共49页.pdf 第12章 ASM - Peterson’s算法 共43页.pdf 第13章 实用互斥算法.具有读-修改-写操作的算法 共72页.pdf ### 知识点总结 #### 一、分布式算法概述及基本概念 - **分布式算法**：涉及多个独立处理单元（节点）之间的通信和协调来共同解决问题的算法。 - **异步网络**：在网络环境中，各个节点之间不存在统一的时钟控制，节点间的通信可能受到延迟的影响，且这些延迟是不可预测的。 #### 二、异步网络算法的特点 - 在异步网络中，假设使用的是可靠的FIFO（先进先出）点对点信道。 - **问题范围**：讨论了同步网络中解决的问题如何适应异步环境，包括： - 环形网络中的领导选举 - 一般网络中的领导选举 - 构建生成树 - 广度优先搜索 - 最短路径 - 最小生成树 #### 三、领导选举算法（环形网络） - **LeLann-Chang-Roberts算法（简称AsynchLCR）**：适用于环形网络的异步领导选举算法。 - **基本思想**： - 将唯一标识符（UID）顺时针发送到环上。 - 节点会丢弃小于自己UID的消息。 - 如果一个节点发现自己的UID返回到了自己，则宣布自己为领导者。 - 正确性分析类似于同步算法，但需要考虑消息在通道中的堆积问题以及单个消息的发送。 #### 四、AsynchLCR算法的实现细节 - **签名**： - 输入：邻居节点i-1发送的UID `rcv(v)i-1,i`。 - 输出：向下一个节点i+1发送UID `send(v)i,i+1`。 - 任务：`leaderi`，宣布自己为领导者。 - **状态变量**： - `u`: 当前节点的UID。 - `send`: FIFO队列，存储待发送的UID。 - `status`: 节点的状态（未知、被选择或报告）。 - **任务描述**： - `send(v)i,i+1`：如果v是队列头部的UID，则移除头部的UID并发送。 - `receive(v)i-1,i`：收到消息后，根据UID更新状态或队列。 - `leaderi`：当节点状态变为被选择时，将状态更改为已报告。 #### 五、AsynchLCR算法的安全性和活性 - **安全性**：除了最大UID对应的节点外，没有其他节点可以执行`leaderi`任务。 - 如果节点i不是最大节点imax，并且对于所有j ∈ [imax, i)，则ui不在sendj中。 - **活性**：最大UID对应的节点最终能够执行`leaderi`任务。 - 通过归纳证明，对于k ∈ [0,n-1]，umax最终会在sendimax+k 或queueimax+k,imax+k+1中出现。 - 使用公平性证明归纳步骤。 #### 六、算法复杂度 - 消息复杂度为O(n²)，因为每个节点都需要与其他所有节点通信。 #### 七、总结 本章介绍了异步网络算法的基础概念及其在环形网络中的应用，重点讲解了AsynchLCR算法的设计原理、实现细节及安全性和活性证明。通过对这些内容的学习，读者可以更好地理解分布式系统中的领导选举机制，并掌握在异步环境下设计高效、安全的分布式算法的基本方法。