2.1分布式算法_基本算法.pptVIP

课程网站;分布协同计算基础;1.分布式算法概述 2. 形式化模型 3.消息传递系统基本算法 生成树上广播和敛播 生成树的构造 4.因果关系和时间 5.选举算法 6.容错一致性;1. 分布式算法概述;异步 不能精确的知道事件发生的绝对时间，甚至相对时间 有限的局部知识 每个计算实体只知道它自己所获得的信息，只是全局情况的一个局部视图。 非确定性 由于系统各组件执行速度的差异,执行通常具有不确定性 故障 各计算实体可能独立发生故障 分布式算法具有更高的不确定性和行为独立性！！ ;处理器数目未知 网络拓扑结构未知 不同位置上的独立输入 几个程序立即运行，在不同的时间开始，以不同的速度运行 处理器的不确定性 不确定的消息传递次数 不确定的消息顺序 处理器和通信故障 幸运的是，并不是每个算法都要面对所有这些不确定性！！;行为很难理解：多处理器并行执行，算法存在多种不同表现。 准确预测算法的行为是不可能的。 否定结论、下界和不可能性结论增加 复杂度分析：通信开销（消息数），故障单元和非故障单元的数量 ;从各种分布式情况中提取基本问题，给出形式化的数学模型 设计解决问题的分布式算法。 算法正确性证明 证明不可能性结果和下限，给出问题如何才能可解的限制以及其求解代价。 算法复杂度分析。 ;2. 形式化模型;消息传递系统模型;消息传递模型;进程和信道建模;配置;事件;进程和信道建模;提交事件;计算事件;计算事件;执行;安全性;异步执行;异步执行;例子 : 洪泛算法;例子: 洪泛算法(续);例子: 洪泛算法(续);不确定性;终止性;复杂性度量;异步系统的时间复杂度;洪泛算法的复杂度;同步消息传递系统;同步模型的例子;同步模型的例子;同步模型的例子;同步洪泛算法的复杂度; ; ;3.消息传递系统基本算法;生成树上的广播;算法步骤示例;生成树上的广播;生成树上的广播;生成树上的广播;复杂性分析; ; ;复杂性分析;敛播;敛播;生成树的构造;生成树的构造; ; ;Initially parent = , children = , and other = . 1: upon receiving no message: 2: if pi = pr and parent = then // root has not yet sent (M) 3: send M to all neighbors 4: parent :=pi, 5: upon receiving M from neighbor pj: 6: if parent = then // pi has not receivedM before 7: parent :=pj 8: send parent to pj 9: send M to all neighbors except pj 10: else send already to pj 11: upon receiving parent from neighbor pj: 12: add pj to children 13: if children U other contains all neighbors except parent then 14: terminate 15: upon receiving already from neighbor pj: 16: add pj to other 17: if children U other contains all neighbors except parent then 18: terminate ; ; ; ; ;生成树算法的执行;生成树算法的执行