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