《分布式計算》教學(xué)大綱

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

2、的大規(guī)模信息處理與計算機應(yīng)用問題，介紹分布式計算中最基本的分布式算法設(shè)計的理論基礎(chǔ)、核心思想、基本概念、基本原理、基本方法、基本技術(shù)以及一些重要的基礎(chǔ)算法，幫助學(xué)生掌握分布式算法領(lǐng)域最基本的知識，使他們能夠運用這些知識解決分布式計算領(lǐng)域內(nèi)一些簡單問題的分布式算法設(shè)計問題，能夠?qū)Ψ植际剿惴ǖ恼_性和復(fù)雜性進(jìn)行分析。通過本課程的學(xué)習(xí)，要求學(xué)生達(dá)到:1通過規(guī)范地完成若干“分布式算法設(shè)計基礎(chǔ)”課程的實驗，進(jìn)一步鞏固所學(xué)的相關(guān)書本知識，在知識、能力、素質(zhì)上得到進(jìn)一步的提高；2有能力閱讀分布式計算領(lǐng)域的一些科技文獻(xiàn)，獨立開展一些分布式算法設(shè)計、分析與應(yīng)用方面的工作，為未來從事分布式計算領(lǐng)域的工作奠定必要的

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

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

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

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

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

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

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

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

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

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