《分布式计算》教学大纲

课程名称：	分布式计算
课程编号：	408413	436414
适用专业：	计算机科学与技术	软件工程
课程类别：	专业任选课	专业任选课
课程学分：	3
总学时：	48
其中：理论学时	36
实验学时	12
先修课程：	高级语言程序设计，数据结构，操作系统，计算机网络，计算机系统结构，算法设计与分析

一、课程的性质、目的与任务

并行与分布式计算是当今计算机科学与技术最为活跃的领域之一，以网络为基础的分布式计算是成本低，应用范围广，具有广阔发展前景的一个重要方向，而分布式算法是深入开展分布式计算的核心基础。

《分布式计算》是计算机科学与技术专业和软件工程专业本科生的专业选修课程。本课程的教学任务和目标是针对以计算机网络为背景的大规模信息处理与计算机应用问题，介绍分布式计算中最基本的分布式算法设计的理论基础、核心思想、基本概念、基本原理、基本方法、基本技术以及一些重要的基础算法，帮助学生掌握分布式算法领域最基本的知识，使他们能够运用这些知识解决分布式计算领域内一些简单问题的分布式算法设计问题，能够对分布式算法的正确性和复杂性进行分析。

通过本课程的学习，要求学生达到:

1．通过规范地完成若干“分布式算法设计基础”课程的实验，进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高；

2．有能力阅读分布式计算领域的一些科技文献，独立开展一些分布式算法设计、分析与应用方面的工作，为未来从事分布式计算领域的工作奠定必要的分布式算法设计基础。

二、课程教学基本内容与要求

第一章 导论：分布式系统

（一）基本教学内容

1.1 分布式系统的定义

1.2 体系结构和语言

1.3 分布式算法

（二）基本要求

教学目的：掌握计算机分布式系统的基本概念、理解计算机体系结构和语言，了解分布式算法。

教学重点：重点讲解分布式系统的定义、体系结构。

教学难点：分布式算法。

第二章 模型

（一）基本教学内容

2.1 转移系统和算法

2.2 转移系统性质的证明

2.3 事件的因果序和逻辑时钟

2.4 附加假设，复杂度

（二）基本要求

教学目的：掌握模型的基本概念、转移系统性质，理解事件的因果序和逻辑时钟，了解附加假设，复杂度。

教学重点：转移系统和算法、事件的因果序和逻辑时钟。

教学难点：转移系统性质的证明。

第三章 通信协议

（一）基本教学内容

3.1 平衡滑动窗口协议

3.2 基于计时器的协议

（二）基本要求

教学目的：理解平衡滑动窗口协议，了解基于计时器的协议机制。

教学重点：基于计时器的协议。

教学难点：平衡滑动窗口协议。

第四章 路由算法

（一）基本教学内容

4.1 基于目的节点的路由

4.2 所有点对之间的最短路径问题

4.3 变更算法

4.4 带有压缩路由表的路由

4.5 分级路由存储管理

（二）基本要求

教学目的：了解基于目的节点的路由，掌握所有点对之间的最短路径问题、变更算法，了解分级路由存储管理技术。

教学重点：所有点对之间的最短路径问题、分级路由存储管理技术。

教学难点：变更算法。

第五章 无死锁的包交换

（一）基本教学内容

5.1 引言

5.2 有结构的方法

5.3 无结构的方法

5.4 需进一步研究的问题

（二）基本要求

教学目的：掌握有结构的、无结构的无死锁的包交换方法。

教学重点：有结构的方法。

教学难点：无结构的方法。

第六章 波动算法与遍历算法

（一）基本教学内容

6.1 波动算法的定义和使用

6.2 波动算法集

6.3 遍历算法

6.4 深度优先搜索的时间复杂度

6.5 遗留问题

（二）基本要求

教学目的：掌握波动算法的定义和使用、波动算法集的基本概念，理解遍历算法和深度优先搜索的时间复杂度，了解波动算法与遍历算法的遗留问题。

教学重点：遍历算法。

教学难点：深度优先搜索的时间复杂度。

第七章 选举算法

（一）基本教学内容

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 确定算法

9.3 概率选举算法

9.4 网络规模计算

（二）基本要求

教学目的：了解匿名网络的确定算法，掌握概率选举算法和网络规模计算。

教学重点：概率选举算法。

教学难点：网络规模计算。

第十章 快照

（一）基本教学内容

10.1 预备知识

10.2 两个快照算法

10.3 使用快照算法

10.4 应用：死锁检测

（二）基本要求

教学目的：了解两个快照算法，掌握快照算法的使用，并进行应用。

教学重点：使用快照算法。

教学难点：应用：死锁检测。

第十一章 方向侦听与定向

（一）基本教学内容

11.1 引言和定义

11.2 环和弦环的选举算法

11.3 超立方体上的计算

11.4 与复杂度有关的问题

11.5 结论和未解决的问题

（二）基本要求

教学目的：掌握环和弦环的选举算法、超立方体上的计算，了解与复杂度有关的问题。

教学重点：环和弦环的选举算法、超立方体上的计算。

教学难点：与复杂度有关的问题。

第十二章 网络中的同步

（一）基本教学内容

12.1 预备知识

12.2 同步网络中的选举

12.3 同步器算法

12.4 应用：广度优先搜索

（二）基本要求

教学目的：掌握同步网络中的选举、同步器算法，了解网络同步的应用广度优先搜索。

教学重点：同步网络中的选举、同步器算法。

教学难点：应用：广度优先搜索。

第十三章 分布式系统中的容错

（一）基本教学内容

13.1 利用容错算法的原因

13.2 健壮算法

13.3 稳定算法

（二）基本要求

教学目的：了解利用容错算法的原因，掌握健壮算法、稳定算法。

教学重点：健壮算法。

教学难点：稳定算法。

第十四章 异步系统中的容错

（一）基本教学内容

14.1 一致性的不可能性

14.2 初始死进程

14.3 确定可实现实例

14.4 概率一致性算法

14.5 弱终止性

（二）基本要求

教学目的：了解初始死进程，掌握概率一致性算法、弱终止性。

教学重点：确定可实现实例。

教学难点：概率一致性算法。

第十五章 同步系统中的容错

（一）基本教学内容

15.1 同步判定协议

15.2 鉴别协议

15.3 时钟同步

（二）基本要求

教学目的：了解同步判定协议，掌握鉴别协议、时钟同步。

教学重点：鉴别协议。

教学难点：时钟同步。

第十六章 故障检测

（一）基本教学内容

16.1 模型和定义

16.2 用弱精确检测器解一致性问题

16.3 最终弱精确检测器

16.4 故障检测器的实现

（二）基本要求

教学目的：了解故障检测的模型和定义，掌握用弱精确检测器解一致性问题、故障检测器的实现。

教学重点：用弱精确检测器解一致性问题。

教学难点：故障检测器的实现。

第十七章 稳定性

（一）基本教学内容

17.1 引言

17.2 图论算法

17.3 稳定方法学

（二）基本要求

教学目的：了解稳定性基本知识，掌握图论算法，了解稳定方法学。

教学重点：图论算法。

教学难点：稳定方法学。

三、课程各章节学时分配

四、本课程课外学习与修学指导

本课程的课外教学内容和形式主要由学生读书，任课教师辅导、答疑、批改作业、实践环节等几部分构成，其中，实践环节的实验教学另行安排教学内容，实验教学内容已经剥离。本课程要求学生在有时间的情况下，尽可能完成教材中所有的习题。学生应在任课教师的帮助下，认真听课，反复思考，大量完成作业，在学习中反复进行阅读、思考、做习题，通过阅读、思考、做习题、分析、联想、概括、归纳、总结等多种有效的方式方法，比较全面、准确地掌握课程的主要内容和教学重点。

课程对学生作业的质量要求是：正确、简洁、规范。“分布式算法设计基础”课程的作业一般有相当的难度。不经过一定数量的习题的练习，要比较深入地掌握“分布式算法设计基础”的主要内容是比较困难的，而且，本课程涉及到过去学生学习过的众多基础课和专业基础课的内容，没有较好的基础，学习本门课程是比较困难的。因此，学生关键是要将过去所学习的知识与本门课程所学的知识建立联系，用心思考，融会贯通，这样，才能从根本上把握课程的要点，体会到分布式计算的精妙之处。

五、本课程考核方式及成绩评定标准

考核方式：开卷考试

成绩评定方法：本课程的考核是平时成绩、实验成绩、期终考试成绩相结合。具体比例为：上课出勤、作业占20%，实验成绩30%，期末考试成绩占50%。

其中期未考试总分100分，基础题占50%，中等难度题占40%，较难题占10%。考试题型主要有：选择题、填空题、简答题、计算题、算法题、分析题、综合应用题等。

六、教材及参考书

教材：《分布式算法导论（第二版）》，（荷）Gerard Tel译者：霍红卫，机械工业出版社，2004.9

主要参考书：

[1]《分布式计算（第二版）》，Hagit Attiya，Jennifer Welch著，骆志刚等译，电子工业出版社，2008.4

[2]《分布式系统概念与设计（英文版，第三版）》，George Coulouris 等，机械工业出版社，2004.1

[3]《分布计算环境》，王柏等，北京邮电大学出版社，北京，2000。

[4]《CORBA系统结构、原理与规范》，OMG编者，韦乐平，电子工业出版社，2000。

[5]《COM原理与应用》，潘爱民，清华大学出版社，2001。

大纲撰写人：李曾妍

大纲审阅人：彭智朝

教学副主任：易叶青

编写日期：2012.6