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

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

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

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

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

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é)重點(diǎn)：有結(jié)構(gòu)的方法。教學(xué)難點(diǎn)：無結(jié)構(gòu)的方法。第六章 波動(dòng)算法與遍歷算法（一）基本教學(xué)內(nèi)容6.1 波動(dòng)算法的定義和使用6.2 波動(dòng)算法集6.3 遍歷算法6.4 深度優(yōu)先搜索的時(shí)間復(fù)雜度6.5 遺留問題（二）基本要求教學(xué)目的：掌握波動(dòng)算法的定義和使用、波動(dòng)算法集的基本概念，理解遍歷算法和深度優(yōu)先搜索的時(shí)間復(fù)雜度，了解波動(dòng)算法與遍歷算法的遺留問題。教學(xué)重點(diǎn)：遍歷算法。教學(xué)難點(diǎn)：深度優(yōu)先搜索的時(shí)間復(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é)重點(diǎn)：korach-kutten-moran算法。教學(xué)難點(diǎn)：選舉算法的環(huán)網(wǎng)和任意網(wǎng)。第八章 終止檢測（一）基本教學(xué)內(nèi)容8.1 預(yù)備知識(shí)8.2 計(jì)算樹和森林8.3 基于波動(dòng)的方法8.4 其他方法（二）基本要求教學(xué)目的：了解終止檢測的計(jì)算樹和森林，掌握基于波動(dòng)的方法。教學(xué)重點(diǎn)：基于波動(dòng)的方法。教學(xué)難點(diǎn)：計(jì)算樹和森林。第九章 匿名網(wǎng)絡(luò)（一）基本教學(xué)內(nèi)容9.1 預(yù)備知識(shí)9.2 確定算法

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

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

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

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

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

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