《分布式計算》教學大綱

1、分布式計算教學大綱課程名稱：分布式計算課程編號：408413436414適用專業(yè)：計算機科學與技術軟件工程課程類別：專業(yè)任選課專業(yè)任選課課程學分：3總學時：48其中：理論學時36實驗學時12先修課程：高級語言程序設計，數據結構，操作系統(tǒng)，計算機網絡，計算機系統(tǒng)結構，算法設計與分析一、課程的性質、目的與任務并行與分布式計算是當今計算機科學與技術最為活躍的領域之一，以網絡為基礎的分布式計算是成本低，應用范圍廣，具有廣闊發(fā)展前景的一個重要方向，而分布式算法是深入開展分布式計算的核心基礎。分布式計算是計算機科學與技術專業(yè)和軟件工程專業(yè)本科生的專業(yè)選修課程。本課程的教學任務和目標是針對以計算機網絡為背景

2、的大規(guī)模信息處理與計算機應用問題，介紹分布式計算中最基本的分布式算法設計的理論基礎、核心思想、基本概念、基本原理、基本方法、基本技術以及一些重要的基礎算法，幫助學生掌握分布式算法領域最基本的知識，使他們能夠運用這些知識解決分布式計算領域內一些簡單問題的分布式算法設計問題，能夠對分布式算法的正確性和復雜性進行分析。通過本課程的學習，要求學生達到:1通過規(guī)范地完成若干“分布式算法設計基礎”課程的實驗，進一步鞏固所學的相關書本知識，在知識、能力、素質上得到進一步的提高；2有能力閱讀分布式計算領域的一些科技文獻，獨立開展一些分布式算法設計、分析與應用方面的工作，為未來從事分布式計算領域的工作奠定必要的

3、分布式算法設計基礎。二、課程教學基本內容與要求第一章 導論：分布式系統(tǒng)（一）基本教學內容1.1 分布式系統(tǒng)的定義1.2 體系結構和語言1.3 分布式算法（二）基本要求教學目的：掌握計算機分布式系統(tǒng)的基本概念、理解計算機體系結構和語言，了解分布式算法。教學重點：重點講解分布式系統(tǒng)的定義、體系結構。教學難點：分布式算法。第二章 模型（一）基本教學內容2.1 轉移系統(tǒng)和算法2.2 轉移系統(tǒng)性質的證明2.3 事件的因果序和邏輯時鐘2.4 附加假設，復雜度（二）基本要求教學目的：掌握模型的基本概念、轉移系統(tǒng)性質，理解事件的因果序和邏輯時鐘，了解附加假設，復雜度。教學重點：轉移系統(tǒng)和算法、事件的因果序和邏

4、輯時鐘。教學難點：轉移系統(tǒng)性質的證明。第三章 通信協(xié)議（一）基本教學內容3.1 平衡滑動窗口協(xié)議3.2 基于計時器的協(xié)議（二）基本要求教學目的：理解平衡滑動窗口協(xié)議，了解基于計時器的協(xié)議機制。教學重點：基于計時器的協(xié)議。教學難點：平衡滑動窗口協(xié)議。第四章 路由算法（一）基本教學內容4.1 基于目的節(jié)點的路由4.2 所有點對之間的最短路徑問題4.3 變更算法4.4 帶有壓縮路由表的路由4.5 分級路由存儲管理（二）基本要求教學目的：了解基于目的節(jié)點的路由，掌握所有點對之間的最短路徑問題、變更算法，了解分級路由存儲管理技術。教學重點：所有點對之間的最短路徑問題、分級路由存儲管理技術。教學難點：變更

5、算法。第五章 無死鎖的包交換（一）基本教學內容5.1 引言5.2 有結構的方法5.3 無結構的方法5.4 需進一步研究的問題（二）基本要求教學目的：掌握有結構的、無結構的無死鎖的包交換方法。教學重點：有結構的方法。教學難點：無結構的方法。第六章 波動算法與遍歷算法（一）基本教學內容6.1 波動算法的定義和使用6.2 波動算法集6.3 遍歷算法6.4 深度優(yōu)先搜索的時間復雜度6.5 遺留問題（二）基本要求教學目的：掌握波動算法的定義和使用、波動算法集的基本概念，理解遍歷算法和深度優(yōu)先搜索的時間復雜度，了解波動算法與遍歷算法的遺留問題。教學重點：遍歷算法。教學難點：深度優(yōu)先搜索的時間復雜度。第七章

6、 選舉算法（一）基本教學內容7.1 引言7.2 環(huán)網7.3 任意網7.4 korach-kutten-moran算法（二）基本要求教學目的：掌握korach-kutten-moran算法，了解選舉算法的環(huán)網和任意網。教學重點：korach-kutten-moran算法。教學難點：選舉算法的環(huán)網和任意網。第八章 終止檢測（一）基本教學內容8.1 預備知識8.2 計算樹和森林8.3 基于波動的方法8.4 其他方法（二）基本要求教學目的：了解終止檢測的計算樹和森林，掌握基于波動的方法。教學重點：基于波動的方法。教學難點：計算樹和森林。第九章 匿名網絡（一）基本教學內容9.1 預備知識9.2 確定算法

7、9.3 概率選舉算法9.4 網絡規(guī)模計算（二）基本要求教學目的：了解匿名網絡的確定算法，掌握概率選舉算法和網絡規(guī)模計算。教學重點：概率選舉算法。教學難點：網絡規(guī)模計算。第十章 快照（一）基本教學內容10.1 預備知識10.2 兩個快照算法10.3 使用快照算法10.4 應用：死鎖檢測（二）基本要求教學目的：了解兩個快照算法，掌握快照算法的使用，并進行應用。教學重點：使用快照算法。教學難點：應用：死鎖檢測。第十一章 方向偵聽與定向（一）基本教學內容11.1 引言和定義11.2 環(huán)和弦環(huán)的選舉算法11.3 超立方體上的計算11.4 與復雜度有關的問題11.5 結論和未解決的問題（二）基本要求教學目

8、的：掌握環(huán)和弦環(huán)的選舉算法、超立方體上的計算，了解與復雜度有關的問題。教學重點：環(huán)和弦環(huán)的選舉算法、超立方體上的計算。教學難點：與復雜度有關的問題。第十二章 網絡中的同步（一）基本教學內容12.1 預備知識12.2 同步網絡中的選舉12.3 同步器算法12.4 應用：廣度優(yōu)先搜索（二）基本要求教學目的：掌握同步網絡中的選舉、同步器算法，了解網絡同步的應用廣度優(yōu)先搜索。教學重點：同步網絡中的選舉、同步器算法。教學難點：應用：廣度優(yōu)先搜索。第十三章 分布式系統(tǒng)中的容錯（一）基本教學內容13.1 利用容錯算法的原因13.2 健壯算法13.3 穩(wěn)定算法（二）基本要求教學目的：了解利用容錯算法的原因，掌

9、握健壯算法、穩(wěn)定算法。教學重點：健壯算法。教學難點：穩(wěn)定算法。第十四章 異步系統(tǒng)中的容錯（一）基本教學內容14.1 一致性的不可能性14.2 初始死進程14.3 確定可實現實例14.4 概率一致性算法14.5 弱終止性（二）基本要求教學目的：了解初始死進程，掌握概率一致性算法、弱終止性。教學重點：確定可實現實例。教學難點：概率一致性算法。第十五章 同步系統(tǒng)中的容錯（一）基本教學內容15.1 同步判定協(xié)議15.2 鑒別協(xié)議15.3 時鐘同步（二）基本要求教學目的：了解同步判定協(xié)議，掌握鑒別協(xié)議、時鐘同步。教學重點：鑒別協(xié)議。教學難點：時鐘同步。第十六章 故障檢測（一）基本教學內容16.1 模型和

10、定義16.2 用弱精確檢測器解一致性問題16.3 最終弱精確檢測器16.4 故障檢測器的實現（二）基本要求教學目的：了解故障檢測的模型和定義，掌握用弱精確檢測器解一致性問題、故障檢測器的實現。教學重點：用弱精確檢測器解一致性問題。教學難點：故障檢測器的實現。第十七章 穩(wěn)定性（一）基本教學內容17.1 引言17.2 圖論算法17.3 穩(wěn)定方法學（二）基本要求教學目的：了解穩(wěn)定性基本知識，掌握圖論算法，了解穩(wěn)定方法學。教學重點：圖論算法。教學難點：穩(wěn)定方法學。三、課程各章節(jié)學時分配序號內容理論學時實驗學時計科網工軟工計科網工軟工1導論：分布式系統(tǒng)222模型223通信協(xié)議444路由算法44225無死

11、鎖的包交換22226波動算法與遍歷算法44227選舉算法44448終止識別22229匿名網絡442210快照222211方向偵聽與定向2212網絡中的同步222213分布式系統(tǒng)中的容錯22合計3636361212四、本課程課外學習與修學指導本課程的課外教學內容和形式主要由學生讀書，任課教師輔導、答疑、批改作業(yè)、實踐環(huán)節(jié)等幾部分構成，其中，實踐環(huán)節(jié)的實驗教學另行安排教學內容，實驗教學內容已經剝離。本課程要求學生在有時間的情況下，盡可能完成教材中所有的習題。學生應在任課教師的幫助下，認真聽課，反復思考，大量完成作業(yè)，在學習中反復進行閱讀、思考、做習題，通過閱讀、思考、做習題、分析、聯(lián)想、概括、歸納

12、、總結等多種有效的方式方法，比較全面、準確地掌握課程的主要內容和教學重點。課程對學生作業(yè)的質量要求是：正確、簡潔、規(guī)范?！胺植际剿惴ㄔO計基礎”課程的作業(yè)一般有相當的難度。不經過一定數量的習題的練習，要比較深入地掌握“分布式算法設計基礎”的主要內容是比較困難的，而且，本課程涉及到過去學生學習過的眾多基礎課和專業(yè)基礎課的內容，沒有較好的基礎，學習本門課程是比較困難的。因此，學生關鍵是要將過去所學習的知識與本門課程所學的知識建立聯(lián)系，用心思考，融會貫通，這樣，才能從根本上把握課程的要點，體會到分布式計算的精妙之處。五、本課程考核方式及成績評定標準考核方式：開卷考試成績評定方法：本課程的考核是平時成績、實驗成績、期終考試成績相結合。具體比例為：上課出勤、作業(yè)占20%，實驗成績30%，期末考試成績占50%。其中期未考試總分100分，基礎題占50%，中等難度題占40%，較難題占10%?？荚囶}型主要有：選擇題、填空題、簡答題、計算題、算法題、分析題、綜合應用題等。六、教材及參考書教材：分布式算法導論（第二版），（荷）Gerard Tel譯者：霍紅衛(wèi)，機械工業(yè)出版社，2004.9主要參考書：1分布式計算（第二版），Hagit Attiya