分布式算法.pptx
《分布式算法.pptx》由会员分享,可在线阅读,更多相关《分布式算法.pptx(179页珍藏版)》请在咨信网上搜索。
1、1Ch.1 导论导论1.1 分布式系统分布式系统nDef:一一个个分分布布式式系系统统是是一一个个能能彼彼此此通通信信的的单单个个计计算算装装置置的的集集合(计算单元:硬合(计算单元:硬处理器;软处理器;软进程)进程)包括:紧耦合系统包括:紧耦合系统-如共享内存多处理机如共享内存多处理机 松散系统松散系统-cow、Internetn与并行处理的分别与并行处理的分别(具有更高程度的不确定性和行为的独立性具有更高程度的不确定性和行为的独立性)v并行处理的目标是使用所有处理器来执行一个大任务并行处理的目标是使用所有处理器来执行一个大任务v而而分分布布式式系系统统中中,每每个个处处理理器器一一般般都都
2、有有自自己己独独立立的的任任务务,但但由由于于各各种种原原因因(为为共共享享资资源源,可可用用性性和和容容错错等等),处处理理机之间需要协调彼此的动作。机之间需要协调彼此的动作。n分布式系统无处不在,其作用是:分布式系统无处不在,其作用是:共享资源共享资源改善性能:并行地解决问题改善性能:并行地解决问题改善可用性:提高可靠性,以防某些成分发生故障改善可用性:提高可靠性,以防某些成分发生故障21.1 分布式系统分布式系统分布式系统软件实例简介nElcomSoft Distributed Password Recovery 是一款俄罗斯安全公司出品的分布式密码是一款俄罗斯安全公司出品的分布式密码暴
3、力破解工具暴力破解工具n能够利用能够利用Nvidia显卡使显卡使WPA和和WPA2无线密无线密钥破解速度提高钥破解速度提高100倍倍n还允许数千台计算机联网进行分布式并行计还允许数千台计算机联网进行分布式并行计算算 31.1 分布式系统分布式系统系统适用范围nElcomSoft 的密码恢复软件主要是面向Office,包括(Word,Excel,Access,Outlook,Outlook Express,VBA,PowerPoint and Visio)n其他的面向微软的产品有(Project,Backup,Mail,Schedule+),archive products(including
4、ZIP,RAR,ACE and ARJ files)等 41.1 分布式系统分布式系统演示界面-支持的文件类型51.1 分布式系统分布式系统演示主界面61.1 分布式系统分布式系统最终破解效果最终破解效果nDOC加密的文档,加密的文档,8位数字型密码小于位数字型密码小于1分钟即可成功解密分钟即可成功解密 71.1 分布式系统分布式系统Agents工作界面 81.1 分布式系统分布式系统NASA SETI寻找外星人计划 nSETI(搜寻外星智慧搜寻外星智慧)是一个寻找地球外智慧生命的科学性实验计划,是一个寻找地球外智慧生命的科学性实验计划,使用射电望远镜来监听太空中的窄频无线电讯号。假设这些讯号
5、中有使用射电望远镜来监听太空中的窄频无线电讯号。假设这些讯号中有些不是自然产生的,那么只要我们侦测到这些讯号就可以证明外星科些不是自然产生的,那么只要我们侦测到这些讯号就可以证明外星科技的存在。技的存在。n射电望远镜讯号主要由噪声射电望远镜讯号主要由噪声(来自天体的发射源与接收者的电子干扰来自天体的发射源与接收者的电子干扰)与像电视转播站、雷达和卫星等等的人工讯号所组成。现代的与像电视转播站、雷达和卫星等等的人工讯号所组成。现代的 Radio SETI 计划会分析这些数字信息。有更强大的运算能力就可以搜寻更计划会分析这些数字信息。有更强大的运算能力就可以搜寻更广泛的频率范围以及提高灵敏度。因此
6、,广泛的频率范围以及提高灵敏度。因此,Radio SETI 计划对运算能计划对运算能力的需求是永无止尽的力的需求是永无止尽的。n原来的原来的 SETI 项目曾经使用望远镜旁专用的超级计算机来进行大量的项目曾经使用望远镜旁专用的超级计算机来进行大量的数据分析。数据分析。1995年,年,David Gedye 提议射电提议射电 SETI 使用由全球联网的使用由全球联网的大量计算机所组成的虚拟超级计算机来进行计算大量计算机所组成的虚拟超级计算机来进行计算,并创建了,并创建了 SETIhome 项目来实验这个想法。项目来实验这个想法。SETIhome 项目于项目于1999年年5月月开始运行。开始运行。
7、91.1 分布式系统分布式系统NASA SETI寻找外星人计划 101.1 分布式系统分布式系统n分布式系统面临的困难分布式系统面临的困难v异质性:异质性:软硬件环境软硬件环境v异步性:异步性:事件发生的绝对、甚至相对时间不可能事件发生的绝对、甚至相对时间不可能总是精确地知道总是精确地知道v局部性:局部性:每个计算实体只有全局情况的一个局部每个计算实体只有全局情况的一个局部视图视图v故障:故障:各计算实体会独立地出故障,影响其他计各计算实体会独立地出故障,影响其他计算实体的工作。算实体的工作。111.2 分布式计算的理论分布式计算的理论n目标:目标:针对分布式系统完成类似于顺序式计算中对算法的
8、研究针对分布式系统完成类似于顺序式计算中对算法的研究v具体:具体:对各种分布式情况发生的对各种分布式情况发生的问题进行抽象问题进行抽象,精确地陈述精确地陈述这些问题这些问题,设计和分析有效算法解决这些问题设计和分析有效算法解决这些问题,证明这些算证明这些算法的最优性法的最优性。n计算模型:计算模型:v通信:通信:计算实体间计算实体间msg传递还是共享变量?传递还是共享变量?v哪些计时信息和行为是可用的?哪些计时信息和行为是可用的?v容许哪些错误容许哪些错误n复杂性度量标准复杂性度量标准v时间,空间时间,空间v通信成本:通信成本:msg的个数,共享变量的大小及个数的个数,共享变量的大小及个数v故
9、障和非故障的数目故障和非故障的数目121.2 分布式计算的理论分布式计算的理论n否定结果、下界和不可能的结果否定结果、下界和不可能的结果 常常要证明在一个特定的分布式系统中,某个特定问常常要证明在一个特定的分布式系统中,某个特定问题的不可解性。题的不可解性。就像就像NP-完全问题一样,表示我们不应该总花精力去完全问题一样,表示我们不应该总花精力去求解这些问题。求解这些问题。当然,可以改变规则,在一种较弱的情况下去求解问当然,可以改变规则,在一种较弱的情况下去求解问题。题。n我们侧重研究:我们侧重研究:v可计算性:可计算性:问题是否可解?问题是否可解?v计算复杂性:计算复杂性:求解问题的代价是什
10、么?求解问题的代价是什么?131.3 理论和实际之关系理论和实际之关系主主要要的的分分布布式式系系统统的的种种类类,分分布布式式计计算算理理论论中中常常用用的形式模型之间的关系的形式模型之间的关系n种类种类v支支持持多多任任务务的的OS:互互斥斥,死死锁锁检检测测和和防防止止等等技技术术在在分分布布式系统中同样存在。式系统中同样存在。vMIMD机机器器:紧紧耦耦合合系系统统,它它由由分分离离的的硬硬件件运运行行共共同同的的软软件件构成。构成。v更更松松散散的的分分布布式式系系统统:由由网网络络(局局域域、广广域域等等)连连接接起起来来的自治主机构成的自治主机构成特特点点是是由由分分离离的的硬硬
11、件件运运行行分分离离的的软软件件。实实体体间间通通过过诸诸如如TCP/IP栈栈、CORBA或或某某些些其其它它组组件件或或中中间间件件等等接接口口互互相相作用。作用。141.3 理论和实际之关系理论和实际之关系n模型模型模模型型太太多多。这这里里主主要要考考虑虑三三种种,基基于于通通信信介介质质和和同同步程度步程度考虑。考虑。异异步步共共享享存存储储模模型型:用用于于紧紧耦耦合合机机器器,通通常常情情况况下下各各处处理理机的时钟信号不是来源于同一信号源机的时钟信号不是来源于同一信号源异步异步msg传递模型:传递模型:用于松散耦合机器及广域网用于松散耦合机器及广域网同同步步msg传传递递模模型型
12、:这这是是一一个个理理想想的的msg传传递递系系统统。该该系系统统中中,某某些些计计时时信信息息(如如msg延延迟迟上上界界)是是已已知知的的,系系统统的执行划分为轮执行,是异步系统的一种特例。的执行划分为轮执行,是异步系统的一种特例。该模型便于设计算法,然后将其翻译成更实际的模型。该模型便于设计算法,然后将其翻译成更实际的模型。lDijkstra E W.Co-operating Sequential Process.In programming Language.F.Genyus(ed.).S.I.:Academic Press,1968,43-112;lOwicki S,Gries D.
13、Verifying Properties of Parallel Programs:An Axiomatic Approach.Communication ACM 19,5(1976),279-285;151.3 理论和实际之关系理论和实际之关系n错误的种类错误的种类v初始死进程初始死进程 指在局部算法中没有执行过一步。指在局部算法中没有执行过一步。vCrash failure崩溃错误崩溃错误(损毁模型损毁模型)指处理机没有任何警告而在某点上停止操作。指处理机没有任何警告而在某点上停止操作。vByzantine failure拜占庭错误拜占庭错误一个出错可引起任意的动作一个出错可引起任意的动作
14、,即执行了与局部算即执行了与局部算法不一致的任意步。拜占庭错误的进程发送的消法不一致的任意步。拜占庭错误的进程发送的消息可能包含任意内容。息可能包含任意内容。16Ch.2 消息传递系统中的基本算法消息传递系统中的基本算法本本章章介介绍绍无无故故障障的的msg传传递递系系统统,考考虑虑两两个个主主要要的的计时模型:同步及异步。计时模型:同步及异步。定定义义主主要要的的复复杂杂性性度度量量、描描述述伪伪代代码码约约定定,最最后后介介绍几个简单算法绍几个简单算法2.1 消息传递系统的形式化模型消息传递系统的形式化模型2.1.1 系统系统1.基本概念基本概念n拓扑:拓扑:无向图无向图 结点结点处理机处
15、理机 边边 双向信道双向信道172.1.1 系统系统n算法:由系统中每个处理器上的局部程序构算法:由系统中每个处理器上的局部程序构成成v局部程序局部程序 执行局部计算执行局部计算本地机器本地机器 发送和接收发送和接收msg邻居邻居v形式地:形式地:一个系统或一个算法是由一个系统或一个算法是由n个处理器个处理器p0,p1,pn-1构成,每个处理器构成,每个处理器pi可以模型化为一个可以模型化为一个具有状态集具有状态集Qi的状态机(可能是无限的)的状态机(可能是无限的)182.1.1 系统系统n状态(进程的局部状态)状态(进程的局部状态)由由pi的变量,的变量,pi的的msgs构成。构成。pi的每
16、个状态由的每个状态由2r个个msg集构成:集构成:voutbufill(1llr):pi经经第第ll条条关关联联的的信信道道发发送送给给邻居,但尚未传到邻居的邻居,但尚未传到邻居的msg。vinbufill(1llr):在在pi的的第第ll条条信信道道上上已已传传递递到到pi,但尚未经,但尚未经pi内部计算步骤处理的内部计算步骤处理的msg。模拟在信道上传输的模拟在信道上传输的msgs 192.1.1 系统系统n初始状态:初始状态:vQi包含一个特殊的初始状态子集:每个包含一个特殊的初始状态子集:每个inbufill必必须为空,但须为空,但outbufill未必为空。未必为空。n转换函数转换函
17、数(transition):处理器处理器pi的转换函数的转换函数(实际上是一个局部程序实际上是一个局部程序)v输入:输入:pi可访问的状态可访问的状态v输出:输出:对每个信道对每个信道ll,至多产生一个,至多产生一个msg输出输出v转换函数使输入缓冲区转换函数使输入缓冲区(1llr)清空。清空。202.1.1 系统系统n配置:配置:配置是分布式系统在某点上整个算法配置是分布式系统在某点上整个算法的全局状态的全局状态向量向量=(q0,q1,qn-1),qi是是pi的一个状态的一个状态一个配置里的一个配置里的outbuf变量的状态表示在通信信道上变量的状态表示在通信信道上传输的信息,由传输的信息,
18、由del事件模拟传输事件模拟传输一个初始的配置是向量一个初始的配置是向量=(q0,q1,qn-1),其中每个其中每个qi是是pi的初始状态,即每个处理器处于初始状态的初始状态,即每个处理器处于初始状态212.1.1 系统系统n事件:事件:系统里所发生的事情均被模型化为事件,对系统里所发生的事情均被模型化为事件,对于于msg传递系统,有两种:传递系统,有两种:comp(i)计算事件。代表处理器计算事件。代表处理器pi的一个计算步的一个计算步骤。其中,骤。其中,pi的转换函数被用于当前可访问状态的转换函数被用于当前可访问状态del(i,j,m)传递事件,表示传递事件,表示msg m从从pi传送到传
19、送到pjn执行:执行:系统在时间上的行为被模型化为一个执行。系统在时间上的行为被模型化为一个执行。它是一个由配置和事件交错的序列。该序列须满足它是一个由配置和事件交错的序列。该序列须满足各种条件,主要分为两类:各种条件,主要分为两类:222.1.1 系统系统 Safety条件条件:(安全性安全性)表表示示某某个个性性质质在在每每次次执执行行中中每每个个可可到到达达的的配配置置里里都必须成立都必须成立在序列的每个有限前缀里必须成立的条件在序列的每个有限前缀里必须成立的条件例例如如:“在在leader选选举举中中,除除了了pmax外外,没没有有哪哪个结点宣称自己是个结点宣称自己是leader”非非
20、形形式式地地:安安全全性性条条件件陈陈述述了了“尚尚未未发发生生坏坏的的情情况况”“坏事从不发生坏事从不发生”232.1.1 系统系统 liveness条件条件:(活跃性活跃性)表示某个性质在每次执行中的某些可达配置里必须成立。表示某个性质在每次执行中的某些可达配置里必须成立。必须成立一定次数的条件必须成立一定次数的条件(可能是无数次可能是无数次)例例如如:条条件件:“p1最最终终须须终终止止”,要要求求p1的的终终止止至至少少发发生生一次;一次;“leader选举,选举,pmax最终宣布自己是最终宣布自己是leader”非形式地,一个活跃条件陈述:非形式地,一个活跃条件陈述:“最终某个好的情
21、况发生最终某个好的情况发生”对特定系统,满足所有要求的安全性条件的序列称为一个对特定系统,满足所有要求的安全性条件的序列称为一个执行执行;若一个执行也满足所有要求的活跃性条件,则称为若一个执行也满足所有要求的活跃性条件,则称为容许容许(合法合法的的)(admissible)执行执行24第二部分第二部分 分布式算法分布式算法汪炀汪炀第二次课第二次课中国科学技术大学计算机系中国科学技术大学计算机系 国家高性能计算中心(合肥)国家高性能计算中心(合肥)252.1.1 系统系统2.异步系统异步系统n异异步步:msg传传递递的的时时间间和和一一个个处处理理器器的的两两个个相相继继步步骤骤之之间间的的时间
22、无固定上界时间无固定上界例例如如,Internet中中,email虽虽然然常常常常是是几几秒秒种种到到达达,但但也也可可能能要要数数天天到到达达。当当然然msg延延迟迟有有上上界界,但但它它可可能能很很大大,且且随随时时间而改变。间而改变。因因此此异异步步算算法法设设计计时时,须须使使之之独独立立于于特特殊殊的的计计时时参参数数,不不能能依赖于该上界。依赖于该上界。n执行片断执行片断一一个个异异步步msg传传递递系系统统的的一一个个执执行行片片断断是是一一个个有有限限或或无无限限的序列:的序列:C0,1,C1,2,C2,3,(C0不一定是初始配置不一定是初始配置)这这里里Ck是是一一个个配配置
23、置,k是是一一个个事事件件。若若是是有有限限的的,则则它它须结束于某个配置,且须满足下述条件:须结束于某个配置,且须满足下述条件:262.1.1 系统系统v若若k=del(i,j,m),则则m必必是是Ck-1里里的的outbufill的的一一个个元元素素,这这里里ll是是pi的信道的信道pi,pj的标号的标号从从Ck-1到到Ck的的唯唯一一变变化化是是将将m从从Ck-1里里的的outbufill中中删删去去,并并将将其加入到其加入到Ck里的里的inbufjh h中,中,h是是pj的信道的信道pi,pj的标号。的标号。即即:传传递递事事件件将将msg从从发发送送者者的的输输出出缓缓冲冲区区移移至
24、至接接收收者者的的输输入入缓冲区。缓冲区。v若若k=comp(i),则从,则从Ck-1到到Ck的变化是的变化是改改变变状状态态:转转换换函函数数在在pi的的可可访访问问状状态态(在在配配置置Ck-1里里)上上进进行行操作,清空操作,清空inbufill,(1llr)发发送送msg:将将转转换换函函数数指指定定的的消消息息集集合合加加到到Ck里里的的变变量量outbufi上。上。(Note:发送发送send,传递,传递delivery之区别之区别)即即:pi以以当当前前状状态态(在在Ck-1中中)为为基基础础按按转转换换函函数数改改变变状状态态并并发发出出msg。272.1.1 系统系统n执执行
25、行:一一个个执执行行是是一一个个执执行行片片断断C0,1,C1,2,这里这里C0是一个初始配置。是一个初始配置。n调调度度:一一个个调调度度(或或调调度度片片段段)总总是是和和执执行行(或或执执行行片片断断)联联系系在在一一起起的的,它它是是执执行行中中的的事事件件序序列列:1,2,。并并非非每每个个事事件件序序列列都都是是调调度度。例例如如,del(1,2,m)不不是是调度,因为此事件之前,调度,因为此事件之前,p1没有步骤发送没有步骤发送(send)m。若若局局部部程程序序是是确确定定的的,则则执执行行(或或执执行行片片断断)就就由由初初始始配配置置C0和和调调度度(或或调调度度片片断断)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分布式 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。