中科大_分布式算法_白色打印版

第二部分分布式算法汪炀中国科学技术大学计算机系国家高性能计算中心（合肥）1Ch.1导论§1.1分布式系统•Def：一个分布式系统是一个能彼此通信的单个计算装置的集合（计算单元：硬——处理器；软——进程）包括：紧耦合系统----如共享内存多处理机松散系统-----cow、Internet•与并行处理的分别(具有更高程度的不确定性和行为的独立性)–并行处理的目标是使用所有处理器来执行一个大任务–而分布式系统中，每个处理器一般都有自己独立的任务，但由于各种原因（为共享资源，可用性和容错等），处理机之间需要协调彼此的动作。•分布式系统无处不在，其作用是：①共享资源②改善性能：并行地解决问题③改善可用性：提高可靠性，以防某些成分发生故障2§1.1分布式系统分布式系统软件实例简介•ElcomSoftDistributedPasswordRecovery是一款俄罗斯安全公司出品的分布式密码暴力破解工具•能够利用Nvidia显卡使WPA和WPA2无线密钥破解速度提高100倍•还允许数千台计算机联网进行分布式并行计算3§1.1分布式系统系统适用范围•ElcomSoft的密码恢复软件主要是面向Office，包括（Word,Excel,Access,Outlook,OutlookExpress,VBA,PowerPointandVisio)•其他的面向微软的产品有（Project,Backup,Mail,Schedule+),archiveproducts(includingZIP,RAR,ACEandARJfiles)等4§1.1分布式系统演示界面-支持的文件类型5§1.1分布式系统演示－主界面6§1.1分布式系统最终破解效果•DOC加密的文档，8位数字型密码小于1分钟即可成功解密7§1.1分布式系统Agents工作界面8§1.1分布式系统NASASETI寻找外星人计划•SETI(搜寻外星智慧)是一个寻找地球外智慧生命的科学性实验计划，使用射电望远镜来监听太空中的窄频无线电讯号。假设这些讯号中有些不是自然产生的，那么只要我们侦测到这些讯号就可以证明外星科技的存在。•射电望远镜讯号主要由噪声(来自天体的发射源与接收者的电子干扰)与像电视转播站、雷达和卫星等等的人工讯号所组成。现代的RadioSETI计划会分析这些数字信息。有更强大的运算能力就可以搜寻更广泛的频率范围以及提高灵敏度。因此，RadioSETI计划对运算能力的需求是永无止尽的。•原来的SETI项目曾经使用望远镜旁专用的超级计算机来进行大量的数据分析。1995年，DavidGedye提议射电SETI使用由全球联网的大量计算机所组成的虚拟超级计算机来进行计算，并创建了SETI@home项目来实验这个想法。SETI@home项目于1999年5月开始运行。9§1.1分布式系统NASASETI寻找外星人计划10§1.1分布式系统•分布式系统面临的困难–异质性：软硬件环境–异步性：事件发生的绝对、甚至相对时间不可能总是精确地知道–局部性：每个计算实体只有全局情况的一个局部视图–故障：各计算实体会独立地出故障，影响其他计算实体的工作。11§1.2分布式计算的理论•目标：针对分布式系统完成类似于顺序式计算中对算法的研究–具体：对各种分布式情况发生的问题进行抽象，精确地陈述这些问题，设计和分析有效算法解决这些问题，证明这些算法的最优性。•计算模型：–通信：计算实体间msg传递还是共享变量？–哪些计时信息和行为是可用的？–容许哪些错误•复杂性度量标准–时间，空间–通信成本：msg的个数，共享变量的大小及个数–故障和非故障的数目12§1.2分布式计算的理论•否定结果、下界和不可能的结果常常要证明在一个特定的分布式系统中，某个特定问题的不可解性。就像NP-完全问题一样，表示我们不应该总花精力去求解这些问题。当然，可以改变规则，在一种较弱的情况下去求解问题。•我们侧重研究：–可计算性：问题是否可解？–计算复杂性：求解问题的代价是什么？13§1.3理论和实际之关系主要的分布式系统的种类，分布式计算理论中常用的形式模型之间的关系•种类–支持多任务的OS：互斥，死锁检测和防止等技术在分布式系统中同样存在。–MIMD机器：紧耦合系统，它由分离的硬件运行共同的软件构成。–更松散的分布式系统：由网络（局域、广域等）连接起来的自治主机构成特点是由分离的硬件运行分离的软件。实体间通过诸如TCP/IP栈、CORBA或某些其它组件或中间件等接口互相作用。14§1.3理论和实际之关系•模型模型太多。这里主要考虑三种，基于通信介质和同步程度考虑。①异步共享存储模型：用于紧耦合机器，通常情况下各处理机的时钟信号不是来源于同一信号源②异步msg传递模型：用于松散耦合机器及广域网③同步msg传递模型：这是一个理想的msg传递系统。该系统中，某些计时信息（如msg延迟上界）是已知的，系统的执行划分为轮执行，是异步系统的一种特例。该模型便于设计算法，然后将其翻译成更实际的模型。15DijkstraEW.Co-operatingSequentialProcess.InprogrammingLanguage.F.Genyus(ed.).[S.I.]:AcademicPress,1968,43-112;OwickiS,GriesD.VerifyingPropertiesofParallelPrograms:AnAxiomaticApproach.CommunicationACM19,5(1976),279-285;§1.3理论和实际之关系•错误的种类–初始死进程指在局部算法中没有执行过一步。–Crashfailure崩溃错误(损毁模型)指处理机没有任何警告而在某点上停止操作。–Byzantinefailure拜占庭错误一个出错可引起任意的动作,即执行了与局部算法不一致的任意步。拜占庭错误的进程发送的消息可能包含任意内容。16Ch.2消息传递系统中的基本算法本章介绍无故障的msg传递系统，考虑两个主要的计时模型：同步及异步。定义主要的复杂性度量、描述伪代码约定，最后介绍几个简单算法§2.1消息传递系统的形式化模型§2.1.1系统1.基本概念•拓扑：无向图结点——处理机边——双向信道17§2.1.1系统•算法：由系统中每个处理器上的局部程序构成–局部程序执行局部计算——本地机器发送和接收msg——邻居–形式地：一个系统或一个算法是由n个处理器p0,p1,…pn-1构成，每个处理器pi可以模型化为一个具有状态集Qi的状态机（可能是无限的）18§2.1.1系统•状态（进程的局部状态）由pi的变量，pi的msgs构成。pi的每个状态由2r个msg集构成：–outbufi[l](1≤l≤r):pi经第l条关联的信道发送给邻居，但尚未传到邻居的msg。–inbufi[l](1≤l≤r):在pi的第l条信道上已传递到pi，但尚未经pi内部计算步骤处理的msg。模拟在信道上传输的msgs19§2.1.1系统•初始状态：–Qi包含一个特殊的初始状态子集：每个inbufi[l]必须为空，但outbufi[l]未必为空。•转换函数(transition)：处理器pi的转换函数(实际上是一个局部程序)–输入：pi可访问的状态–输出：对每个信道l，至多产生一个msg输出–转换函数使输入缓冲区(1≤l≤r)清空。20§2.1.1系统•配置：配置是分布式系统在某点上整个算法的全局状态向量=(q0,q1,…qn-1),qi是pi的一个状态一个配置里的outbuf变量的状态表示在通信信道上传输的信息，由del事件模拟传输一个初始的配置是向量=(q0,q1,…qn-1),其中每个qi是pi的初始状态，即每个处理器处于初始状态21§2.1.1系统•事件：系统里所发生的事情均被模型化为事件，对于msg传递系统，有两种：comp(i)——计算事件。代表处理器pi的一个计算步骤。其中，pi的转换函数被用于当前可访问状态del(i,j,m)——传递事件，表示msgm从pi传送到pj•执行：系统在时间上的行为被模型化为一个执行。它是一个由配置和事件交错的序列。该序列须满足各种条件，主要分为两类：22§2.1.1系统①Safety条件：(安全性)表示某个性质在每次执行中每个可到达的配置里都必须成立在序列的每个有限前缀里必须成立的条件例如：“在leader选举中，除了pmax外，没有哪个结点宣称自己是leader”非形式地：安全性条件陈述了“尚未发生坏的情况”“坏事从不发生”23§2.1.1系统②liveness条件：(活跃性)表示某个性质在每次执行中的某些可达配置里必须成立。必须成立一定次数的条件(可能是无数次)例如：条件：“p1最终须终止”，要求p1的终止至少发生一次；“leader选举，pmax最终宣布自己是leader”非形式地，一个活跃条件陈述：“最终某个好的情况发生”对特定系统，满足所有要求的安全性条件的序列称为一个执行;若一个执行也满足所有要求的活跃性条件，则称为容许(合法的)(admissible)执行24第二部分分布式算法汪炀第二次课中国科学技术大学计算机系国家高性能计算中心（合肥）1§2.1.1系统2.异步系统•异步：msg传递的时间和一个处理器的两个相继步骤之间的时间无固定上界例如，Internet中，email虽然常常是几秒种到达，但也可能要数天到达。当然msg延迟有上界，但它可能很大，且随时间而改变。因此异步算法设计时，须使之独立于特殊的计时参数，不能依赖于该上界。•执行片断一个异步msg传递系统的一个执行片断α是一个有限或无限的序列：C0,Φ1,C1,Φ2,C2,Φ3,…,(C0不一定是初始配置)这里Ck是一个配置，Φk是一个事件。若α是有限的，则它须结束于某个配置，且须满足下述条件：2§2.1.1系统–若Φk=del(i,j,m)，则m必是Ck-1里的outbufi[l]的一个元素，这里l是pi的信道{pi,pj}的标号从Ck-1到Ck的唯一变化是将m从Ck-1里的outbufi[l]中删去，并将其加入到Ck里的inbufj[h]中，h是pj的信道{pi,pj}的标号。即：传递事件将msg从发送者的输出缓冲区移至接收者的输入缓冲区。–若Φk=comp(i)，则从Ck-1到Ck的变化是①改变状态：转换函数在pi的可访问状态(在配置Ck-1里)上进行操作，清空inbufi[l]，(1≤l≤r)②发送msg：将转换函数指定的消息集合加到Ck里的变量outbufi上。(Note:发送send，传递delivery之区别)即：pi以当前状态(在Ck-1中)为基础按转换函数改变状态并发出msg。3§2.1.1系统•执行：一个执行是一个执行片断C0,Φ1,C1,Φ2,…,这里C0是一个初始配置。•调度：一个调度(或调度片段)总是和执行(或执行片断)联系在一起的，它是执行中的事件序列：Φ1,Φ2,…。并非每个事件序列都是调度。例如，del(1,2,m)不是调度，因为此事件之前，p1没有步骤发送(send)m。若局部程序是确定的，则执行(或执行片断)就由初始配置C0和调度(或调度片断)σ唯一确定，可表示为exec(C0,σ)。4§2.1.1系统•容许执行：(满足活跃性条件)异步系统中，若某个处理器有无限个计算事件，每个发送的msg都最终被传递，则执行称为容许的。Note:无限个计算事件是指处理器没有出错，但它不蕴含处理器的局部程序必须包括一个无限循环非形式地说：一个算法终止是指在某点后转换函数不改变处理器的状态。•容许的调度：若它是一个容许执行的调度。5§2.1.1系统3.同步系统在同步模型中，处理器按锁步骤(lock-step)执行：执行被划分为轮，每轮里，①每个处理器能够发送一个msg到每个邻居，这些msg被传递。②每个处理器一接到msg就进行计算。虽然特殊的分布系统里一般达不到，但这种模型对于设计算法非常方便，因为无需和更多的不确定性打交道。当按此模型设计算法后，能够很容易模拟得到异步算法。•轮：在同步系统中，配置和事件序列可以划分成不相交的轮，每轮由一个传递事件(