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

《中科大_分布式算法_白色打印版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二部分分布式算法汪炀中国科学技术大学计算机系国家高性能计算中心（合肥）1Ch.1导论§1.1分布式系统•Def：一个分布式系统是一个能彼此通信的单个计算装置的集合（计算单元：硬——处理器；软——进程）包括：紧耦合系统----如共享内存多处理机松散系统-----cow、Internet•与并行处理的分别(具有更高程度的不确定性和行为的独立性)–并行处理的目标是使用所有处理器来执行一个大任务–而分布式系统中，每个处理器一般都有自己独立的任务，但由于各种原因（为共享资源，可用性和容错等），处理机之间需要协调彼此的动作。•分布式系统无处不在，其作用是：①共享资源②改善性能：并行地解决问题

2、③改善可用性：提高可靠性，以防某些成分发生故障2§1.1分布式系统分布式系统软件实例简介•ElcomSoftDistributedPasswordRecovery是一款俄罗斯安全公司出品的分布式密码暴力破解工具•能够利用Nvidia显卡使WPA和WPA2无线密钥破解速度提高100倍•还允许数千台计算机联网进行分布式并行计算3§1.1分布式系统系统适用范围•ElcomSoft的密码恢复软件主要是面向Office，包括（Word,Excel,Access,Outlook,OutlookExpress,VBA,PowerPointandVisio)•其他的面向微软的产品有（Project

3、,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(搜寻外星智慧)是一个寻找地球外智慧生命的科学性实验计划，使用射电望远镜来监听太空中的窄频无线电讯号。假设这些讯号中有些不是自然产生的，那么只要我们侦测到这些讯号就可以证明外星科

4、技的存在。•射电望远镜讯号主要由噪声(来自天体的发射源与接收者的电子干扰)与像电视转播站、雷达和卫星等等的人工讯号所组成。现代的RadioSETI计划会分析这些数字信息。有更强大的运算能力就可以搜寻更广泛的频率范围以及提高灵敏度。因此，RadioSETI计划对运算能力的需求是永无止尽的。•原来的SETI项目曾经使用望远镜旁专用的超级计算机来进行大量的数据分析。1995年，DavidGedye提议射电SETI使用由全球联网的大量计算机所组成的虚拟超级计算机来进行计算，并创建了SETI@home项目来实验这个想法。SETI@home项目于1999年5月开始运行。9§1.1分布式系统NA

5、SASETI寻找外星人计划10§1.1分布式系统•分布式系统面临的困难–异质性：软硬件环境–异步性：事件发生的绝对、甚至相对时间不可能总是精确地知道–局部性：每个计算实体只有全局情况的一个局部视图–故障：各计算实体会独立地出故障，影响其他计算实体的工作。11§1.2分布式计算的理论•目标：针对分布式系统完成类似于顺序式计算中对算法的研究–具体：对各种分布式情况发生的问题进行抽象，精确地陈述这些问题，设计和分析有效算法解决这些问题，证明这些算法的最优性。•计算模型：–通信：计算实体间msg传递还是共享变量？–哪些计时信息和行为是可用的？–容许哪些错误•复杂性度量标准–时间，空间–通信

6、成本：msg的个数，共享变量的大小及个数–故障和非故障的数目12§1.2分布式计算的理论•否定结果、下界和不可能的结果常常要证明在一个特定的分布式系统中，某个特定问题的不可解性。就像NP-完全问题一样，表示我们不应该总花精力去求解这些问题。当然，可以改变规则，在一种较弱的情况下去求解问题。•我们侧重研究：–可计算性：问题是否可解？–计算复杂性：求解问题的代价是什么？13§1.3理论和实际之关系主要的分布式系统的种类，分布式计算理论中常用的形式模型之间的关系•种类–支持多任务的OS：互斥，死锁检测和防止等技术在分布式系统中同样存在。–MIMD机器：紧耦合系统，它由分离的硬件运行共同的

7、软件构成。–更松散的分布式系统：由网络（局域、广域等）连接起来的自治主机构成特点是由分离的硬件运行分离的软件。实体间通过诸如TCP/IP栈、CORBA或某些其它组件或中间件等接口互相作用。14§1.3理论和实际之关系•模型模型太多。这里主要考虑三种，基于通信介质和同步程度考虑。①异步共享存储模型：用于紧耦合机器，通常情况下各处理机的时钟信号不是来源于同一信号源②异步msg传递模型：用于松散耦合机器及广域网③同步msg传递模型：这是一个理想的msg传递系统。该系统中，某