21分布式算法(1)-基本算法-课件【PPT讲稿】.ppt

课程网站? http://dcwikineu. 分布协同计算基础第二章: 分布式算法(1) 张锡哲副教授计算机应用技术研究所东北大学信息科学与工程学院? ? ? ?生成树上广播和敛播?生成树的构造? ? ? ?异步?不能精确的知道事件发生的绝对时间,甚至相对时间?有限的局部知识?每个计算实体只知道它自己所获得的信息,只是全局情况的一个局部视图。?非确定性?由于系统各组件执行速度的差异,执行通常具有不确定性?故障?各计算实体可能独立发生故障?分布式算法具有更高的不确定性和行为独立性!! 5分布式计算的困难?处理器数目未知?网络拓扑结构未知?不同位置上的独立输入?几个程序立即运行,在不同的时间开始,以不同的速度运行?处理器的不确定性?不确定的消息传递次数?不确定的消息顺序?处理器和通信故障?幸运的是,并不是每个算法都要面对所有这些不确定性!! 6不确定性和行为独立性?行为很难理解:多处理器并行执行,算法存在多种不同表现。?准确预测算法的行为是不可能的。?否定结论、下界和不可能性结论增加?复杂度分析:通信开销(消息数),故障单元和非故障单元的数量 7分布式计算的特点?从各种分布式情况中提取基本问题,给出形式化的数学模型?设计解决问题的分布式算法。?算法正确性证明?证明不可能性结果和下限,给出问题如何才能可解的限制以及其求解代价。?算法复杂度分析。 8研究分布式算法的方法 ?消息传递系统模型由一组位于有向网络图节点位置的计算元素组成。?表示为 G(V,E), 其中节点集 V={ p 0, p 1, …, p n-1…}代表进程的集合,边集 E代表间的信道的集合。?每个进程 p i用整数 1~r标记与之相连的信道,其中 r是 p i的度。?算法由各进程上的局部程序所组成。