《分布式计算》教学大纲

1、分布式计算教学大纲课程名称：分布式计算课程编号：408413436414适用专业：计算机科学与技术软件工程课程类别：专业任选课专业任选课课程学分：3总学时：48其中：理论学时36实验学时12先修课程：高级语言程序设计，数据结构，操作系统，计算机网络，计算机系统结构，算法设计与分析一、课程的性质、目的与任务并行与分布式计算是当今计算机科学与技术最为活跃的领域之一，以网络为基础的分布式计算是成本低，应用范围广，具有广阔发展前景的一个重要方向，而分布式算法是深入开展分布式计算的核心基础。分布式计算是计算机科学与技术专业和软件工程专业本科生的专业选修课程。本课程的教学任务和目标是针对以计算机网络为背景

2、的大规模信息处理与计算机应用问题，介绍分布式计算中最基本的分布式算法设计的理论基础、核心思想、基本概念、基本原理、基本方法、基本技术以及一些重要的基础算法，帮助学生掌握分布式算法领域最基本的知识，使他们能够运用这些知识解决分布式计算领域内一些简单问题的分布式算法设计问题，能够对分布式算法的正确性和复杂性进行分析。通过本课程的学习，要求学生达到:1通过规范地完成若干“分布式算法设计基础”课程的实验，进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高；2有能力阅读分布式计算领域的一些科技文献，独立开展一些分布式算法设计、分析与应用方面的工作，为未来从事分布式计算领域的工作奠定必要的

3、分布式算法设计基础。二、课程教学基本内容与要求第一章 导论：分布式系统（一）基本教学内容1.1 分布式系统的定义1.2 体系结构和语言1.3 分布式算法（二）基本要求教学目的：掌握计算机分布式系统的基本概念、理解计算机体系结构和语言，了解分布式算法。教学重点：重点讲解分布式系统的定义、体系结构。教学难点：分布式算法。第二章 模型（一）基本教学内容2.1 转移系统和算法2.2 转移系统性质的证明2.3 事件的因果序和逻辑时钟2.4 附加假设，复杂度（二）基本要求教学目的：掌握模型的基本概念、转移系统性质，理解事件的因果序和逻辑时钟，了解附加假设，复杂度。教学重点：转移系统和算法、事件的因果序和逻

4、辑时钟。教学难点：转移系统性质的证明。第三章 通信协议（一）基本教学内容3.1 平衡滑动窗口协议3.2 基于计时器的协议（二）基本要求教学目的：理解平衡滑动窗口协议，了解基于计时器的协议机制。教学重点：基于计时器的协议。教学难点：平衡滑动窗口协议。第四章 路由算法（一）基本教学内容4.1 基于目的节点的路由4.2 所有点对之间的最短路径问题4.3 变更算法4.4 带有压缩路由表的路由4.5 分级路由存储管理（二）基本要求教学目的：了解基于目的节点的路由，掌握所有点对之间的最短路径问题、变更算法，了解分级路由存储管理技术。教学重点：所有点对之间的最短路径问题、分级路由存储管理技术。教学难点：变更

5、算法。第五章 无死锁的包交换（一）基本教学内容5.1 引言5.2 有结构的方法5.3 无结构的方法5.4 需进一步研究的问题（二）基本要求教学目的：掌握有结构的、无结构的无死锁的包交换方法。教学重点：有结构的方法。教学难点：无结构的方法。第六章 波动算法与遍历算法（一）基本教学内容6.1 波动算法的定义和使用6.2 波动算法集6.3 遍历算法6.4 深度优先搜索的时间复杂度6.5 遗留问题（二）基本要求教学目的：掌握波动算法的定义和使用、波动算法集的基本概念，理解遍历算法和深度优先搜索的时间复杂度，了解波动算法与遍历算法的遗留问题。教学重点：遍历算法。教学难点：深度优先搜索的时间复杂度。第七章

6、 选举算法（一）基本教学内容7.1 引言7.2 环网7.3 任意网7.4 korach-kutten-moran算法（二）基本要求教学目的：掌握korach-kutten-moran算法，了解选举算法的环网和任意网。教学重点：korach-kutten-moran算法。教学难点：选举算法的环网和任意网。第八章 终止检测（一）基本教学内容8.1 预备知识8.2 计算树和森林8.3 基于波动的方法8.4 其他方法（二）基本要求教学目的：了解终止检测的计算树和森林，掌握基于波动的方法。教学重点：基于波动的方法。教学难点：计算树和森林。第九章 匿名网络（一）基本教学内容9.1 预备知识9.2 确定算法

7、9.3 概率选举算法9.4 网络规模计算（二）基本要求教学目的：了解匿名网络的确定算法，掌握概率选举算法和网络规模计算。教学重点：概率选举算法。教学难点：网络规模计算。第十章 快照（一）基本教学内容10.1 预备知识10.2 两个快照算法10.3 使用快照算法10.4 应用：死锁检测（二）基本要求教学目的：了解两个快照算法，掌握快照算法的使用，并进行应用。教学重点：使用快照算法。教学难点：应用：死锁检测。第十一章 方向侦听与定向（一）基本教学内容11.1 引言和定义11.2 环和弦环的选举算法11.3 超立方体上的计算11.4 与复杂度有关的问题11.5 结论和未解决的问题（二）基本要求教学目

8、的：掌握环和弦环的选举算法、超立方体上的计算，了解与复杂度有关的问题。教学重点：环和弦环的选举算法、超立方体上的计算。教学难点：与复杂度有关的问题。第十二章 网络中的同步（一）基本教学内容12.1 预备知识12.2 同步网络中的选举12.3 同步器算法12.4 应用：广度优先搜索（二）基本要求教学目的：掌握同步网络中的选举、同步器算法，了解网络同步的应用广度优先搜索。教学重点：同步网络中的选举、同步器算法。教学难点：应用：广度优先搜索。第十三章 分布式系统中的容错（一）基本教学内容13.1 利用容错算法的原因13.2 健壮算法13.3 稳定算法（二）基本要求教学目的：了解利用容错算法的原因，掌

9、握健壮算法、稳定算法。教学重点：健壮算法。教学难点：稳定算法。第十四章 异步系统中的容错（一）基本教学内容14.1 一致性的不可能性14.2 初始死进程14.3 确定可实现实例14.4 概率一致性算法14.5 弱终止性（二）基本要求教学目的：了解初始死进程，掌握概率一致性算法、弱终止性。教学重点：确定可实现实例。教学难点：概率一致性算法。第十五章 同步系统中的容错（一）基本教学内容15.1 同步判定协议15.2 鉴别协议15.3 时钟同步（二）基本要求教学目的：了解同步判定协议，掌握鉴别协议、时钟同步。教学重点：鉴别协议。教学难点：时钟同步。第十六章 故障检测（一）基本教学内容16.1 模型和

10、定义16.2 用弱精确检测器解一致性问题16.3 最终弱精确检测器16.4 故障检测器的实现（二）基本要求教学目的：了解故障检测的模型和定义，掌握用弱精确检测器解一致性问题、故障检测器的实现。教学重点：用弱精确检测器解一致性问题。教学难点：故障检测器的实现。第十七章 稳定性（一）基本教学内容17.1 引言17.2 图论算法17.3 稳定方法学（二）基本要求教学目的：了解稳定性基本知识，掌握图论算法，了解稳定方法学。教学重点：图论算法。教学难点：稳定方法学。三、课程各章节学时分配序号内容理论学时实验学时计科网工软工计科网工软工1导论：分布式系统222模型223通信协议444路由算法44225无死

11、锁的包交换22226波动算法与遍历算法44227选举算法44448终止识别22229匿名网络442210快照222211方向侦听与定向2212网络中的同步222213分布式系统中的容错22合计3636361212四、本课程课外学习与修学指导本课程的课外教学内容和形式主要由学生读书，任课教师辅导、答疑、批改作业、实践环节等几部分构成，其中，实践环节的实验教学另行安排教学内容，实验教学内容已经剥离。本课程要求学生在有时间的情况下，尽可能完成教材中所有的习题。学生应在任课教师的帮助下，认真听课，反复思考，大量完成作业，在学习中反复进行阅读、思考、做习题，通过阅读、思考、做习题、分析、联想、概括、归纳

12、、总结等多种有效的方式方法，比较全面、准确地掌握课程的主要内容和教学重点。课程对学生作业的质量要求是：正确、简洁、规范。“分布式算法设计基础”课程的作业一般有相当的难度。不经过一定数量的习题的练习，要比较深入地掌握“分布式算法设计基础”的主要内容是比较困难的，而且，本课程涉及到过去学生学习过的众多基础课和专业基础课的内容，没有较好的基础，学习本门课程是比较困难的。因此，学生关键是要将过去所学习的知识与本门课程所学的知识建立联系，用心思考，融会贯通，这样，才能从根本上把握课程的要点，体会到分布式计算的精妙之处。五、本课程考核方式及成绩评定标准考核方式：开卷考试成绩评定方法：本课程的考核是平时成绩、实验成绩、期终考试成绩相结合。具体比例为：上课出勤、作业占20%，实验成绩30%，期末考试成绩占50%。其中期未考试总分100分，基础题占50%，中等难度题占40%，较难题占10%。考试题型主要有：选择题、填空题、简答题、计算题、算法题、分析题、综合应用题等。六、教材及参考书教材：分布式算法导论（第二版），（荷）Gerard Tel译者：霍红卫，机械工业出版社，2004.9主要参考书：1分布式计算（第二版），Hagit Attiya