分布式算法導(dǎo)論（原書第2版）

第1章  導(dǎo)論：分布式系統(tǒng)
 1. 1  分布式系統(tǒng)的定義
 1. 1. 1  動(dòng)機(jī)
 1. 2  計(jì)算機(jī)網(wǎng)絡(luò)
 1. 1. 3  廣域網(wǎng)絡(luò)
 1. 1. 4  局域網(wǎng)
 1. 1. 5  多處理器計(jì)算機(jī)
 1. 1. 6  協(xié)同操作進(jìn)程
 1. 2  體系結(jié)構(gòu)和語(yǔ)言
 1. 2. 1  結(jié)構(gòu)
 1. 2. 2  0SI參考模型
 1. 2. 3  局域網(wǎng)絡(luò)OSI模型：IEEE標(biāo)準(zhǔn)
 1. 2. 4  語(yǔ)言支持
 1. 3  分布式算法
 1. 3. 1  分布式算法與集中式算法
 1. 3. 2  一個(gè)例子：?jiǎn)蜗⑼ㄐ?br /> 1. 3. 3  研究領(lǐng)域
 1. 4  本書概要
 第一部分  協(xié)  議
 第2章  模型
 2. 1  轉(zhuǎn)移系統(tǒng)和算法
 2. 1. 1  轉(zhuǎn)移系統(tǒng)
 2. 1. 2  異步消息傳遞系統(tǒng)
 2. 1. 3  同步消息傳遞系統(tǒng)
 2. 1. 4  公平性
 2. 2  轉(zhuǎn)移系統(tǒng)性質(zhì)的證明
 2. 2. 1  安全性
 2. 2. 2  活動(dòng)性
 2. 3  事件的因果序和邏輯時(shí)鐘
 2. 3. 1  事件的獨(dú)立性和相關(guān)性
 2. 3. 2  執(zhí)行的等價(jià)性：計(jì)算
 2. 3. 3  邏輯時(shí)鐘
 2. 4  附加假設(shè), 復(fù)雜度
 2. 4. 1  網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)
 2. 4. 2  信道性質(zhì)
 2. 4. 3  實(shí)時(shí)性假設(shè)
 2. 4. 4  進(jìn)程知識(shí)
 2. 4. 5  分布式算法的復(fù)雜度
 習(xí)題
 第3章  通信協(xié)議
 3. 1  平衡滑動(dòng)窗口協(xié)議
 3. 1. 1  協(xié)議表示
 3. 1. 2  協(xié)議的正確性證明
 3. 1. 3  協(xié)議討論
 3. 2  基于計(jì)時(shí)器的協(xié)議
 3. 2. 1  協(xié)議表示
 3. 2. 2  協(xié)議的正確性證明
 3. 2. 3  協(xié)議討論
 習(xí)題
 第4章  路由算法
 4. 1  基于目的節(jié)點(diǎn)的路由
 4. 2  所有點(diǎn)對(duì)之間的最短路徑問(wèn)題
 4. 2. 1  Floyd-Warshall算法
 4. 2. 2  Toueg最短路徑算法
 4. 2. 3  討論以及更多算法
 4. 3  變更算法
 4. 3. 1  算法描述
 4. 3. 2  變更算法的正確性
 4. 3. 3  算法討論
 4. 4  帶有壓縮路由表的路由
 4. 4. 1  樹(shù)標(biāo)號(hào)模式
 4. 4. 2  區(qū)間路由
 4. 4. 3  前綴路由
 4. 5  分級(jí)路由
 習(xí)題
 第5章  無(wú)死鎖的包交換
 5. 1  引言
 5. 2  有結(jié)構(gòu)的方法
 5. 2. 1  緩沖圖
 5. 2. 2  圖G的定向
 5. 3  無(wú)結(jié)構(gòu)的方法
 5. 3. 1  前向計(jì)數(shù)控制器和后向計(jì)數(shù)
 控制器
 5. 3. 2  前向狀態(tài)控制器和后向狀態(tài)
 控制器
 5. 4  需進(jìn)一步研究的問(wèn)題
 5. 4. 1  拓?fù)渥兓?br /> 5. 4. 2  其他類型的死鎖
 5. 4. 3  活鎖
 習(xí)題
 第二部分  基本算法
 第6章  波動(dòng)算法與遍歷算法
 6. 1  波動(dòng)算法的定義和使用
 6. 1. 1  波動(dòng)算法定義
 6. 1. 2  波動(dòng)算法的一些基本結(jié)果
 6. 1. 3  具有反饋的信息傳播
 6. 1. 4  同步
 6. 1. 5  計(jì)算下確界函數(shù)
 6. 2  波動(dòng)算法集
 6. 2. 1  環(huán)網(wǎng)算法
 6. 2. 2  樹(shù)算法
 6. 2. 3  回波算法
 6. 2. 4  輪詢算法
 6. 2. 5  相位算法
 6. 2. 6  Finn算法
 6. 3  遍歷算法
 6. 3. 1  遍歷團(tuán)
 6. 3. 2  遍歷圓環(huán)
 6. 3. 3  遍歷超立方體
 6. 3. 4  遍歷連通網(wǎng)絡(luò)
 6. 4  深度優(yōu)先搜索的時(shí)間復(fù)雜度
 6. 4. 1  分布式深度優(yōu)先搜索
 6. 4. 2  線性時(shí)間的深度優(yōu)先搜索算法
 6. 4. 3  具有近鄰知識(shí)的深度優(yōu)先搜索
 6. 5  遺留問(wèn)題
 6. 5. 1  波動(dòng)算法綜述
 6. 5. 2  計(jì)算和
 6. 5. 3  時(shí)間復(fù)雜度的另一種定義
 習(xí)題
 第7章  選舉算法
 7. 1  引言
 7. 1. 1  本章所做假設(shè)
 7. 1. 2  選舉和波動(dòng)
 7. 2  環(huán)網(wǎng)
 7. 2. 1  LeLann和Chang-Roberts算法
 7. 2. 2  Peterson／Dolev-Klawe-Rodeh算法
 7. 2. 3  一個(gè)下界
 7. 3  任意網(wǎng)
 7. 3. 1  廢止和快速算法
 7. 3. 2  Gallager-Humblet-Spira算法
 7. 3. 3  GHS算法的全局描述
 7. 3. 4  GHS算法的詳細(xì)描述
 7. 3. 5  GHS算法的討論和變化
 7. 4  Korach-Kutten-Moran算法
 7. 4. 1  模塊構(gòu)造
 7. 4. 2  KKM算法的應(yīng)用
 習(xí)題
 第8章  終止檢測(cè)
 8. 1  預(yù)備知識(shí)
 8. 1. 1  定義
 8. 1. 2  兩個(gè)下界
 8. 1. 3  終止進(jìn)程
 8. 2  計(jì)算樹(shù)和森林
 8. 2. 1  Dijkstra-Scholten算法
 8. 2. 2  Shavit-Francez算法
 8. 3  基于波動(dòng)的方法
 8. 3. 1  Dijkstra-Feijen-VanGasteren算法
 8. 3. 2  基本消息的計(jì)數(shù)：Safra算法
 8. 3. 3  利用確認(rèn)
 8. 3. 4  帶波動(dòng)的終止檢測(cè)
 8. 4  其他方法
 8. 4. 1  信用-恢復(fù)算法
 8. 4. 2  基于時(shí)戳的終止檢測(cè)方法
 習(xí)題
 第9章  匿名網(wǎng)絡(luò)
 9. 1  預(yù)備知識(shí)
 9. 1. 1  定義
 9. 1. 2  概率算法的分類
 9. 1. 3  本章考慮的問(wèn)題
 9. 1. 4  同步消息傳遞與異步消息傳遞
 9. 2  確定算法
 9. 2. 1  確定性的選舉：否定性的結(jié)果
 9. 2. 2  環(huán)上函數(shù)計(jì)算
 9. 3  概率選舉算法
 9. 4  網(wǎng)絡(luò)規(guī)模計(jì)算
 9. 4. 1  否定性結(jié)果
 9. 4. 2  計(jì)算環(huán)規(guī)模的算法
 習(xí)題
 第10章  快照
 10. 1  預(yù)備知識(shí)
 10. 2  兩個(gè)快照算法
 10. 2. 1  Chandy-Lamport算法
 10. 2. 2  Lai-Yang算法
 10. 3  使用快照算法
 10. 3. 1  計(jì)算信道狀態(tài)
 10. 3. 2  快照的適時(shí)性
 10. 3. 3  穩(wěn)定性檢測(cè)
 10. 4  應(yīng)用：死鎖檢測(cè)
 10. 4. 1  基本計(jì)算模型和問(wèn)題闡述
 10. 4. 2  全局-標(biāo)記算法
 10. 4. 3  受限模型的死鎖檢測(cè)
 習(xí)題
 第11章  方向偵聽(tīng)與定向
 11. 1  引言和定義
 11. 1. 1  方向偵聽(tīng)的定義和特性
 11. 1. 2  利用方向偵聽(tīng)
 11. 1. 3  具有方向偵聽(tīng)的廣播
 11. 2  環(huán)和弦環(huán)的選舉算法
 11. 2. 1  Franklin算法
 11. 2. 2  Attiya改進(jìn)
 11. 2. 3  最小化弦數(shù)
 11. 2. 4  1-弦線性算法
 11. 3  超立方體上的計(jì)算
 11. 3. 1  基線：沒(méi)有拓?fù)渲R(shí)
 11. 3. 2  進(jìn)行比賽的算法
 11. 3. 3  多路徑流量算法
 11. 3. 4  使用掩碼的有效超立方體算法
 11. 3. 5  無(wú)標(biāo)號(hào)超立方體上的選舉算法
 11. 4  與復(fù)雜度有關(guān)的問(wèn)題
 11. 4. 1  團(tuán)或任意圖的定向
 11. 4. 2  位復(fù)雜度和多路徑流量算法
 11. 4. 3  Verweij隨機(jī)漫步算法
 11. 5  結(jié)論和未解決的問(wèn)題
 11. 5. 1  利用方向偵聽(tīng)
 11. 5. 2  復(fù)雜度歸約
 11. 5. 3  當(dāng)前研究
 習(xí)題
 第12章  網(wǎng)絡(luò)中的同步
 12. 1  預(yù)備知識(shí)
 12. 1. 1  同步網(wǎng)絡(luò)
 12. 1. 2  通過(guò)同步提高效率
 12. 1. 3  異步有限延遲網(wǎng)絡(luò)
 12. 2  同步網(wǎng)絡(luò)中的選舉
 12. 2. 1  網(wǎng)絡(luò)規(guī)模已知
 12. 2. 2  網(wǎng)絡(luò)規(guī)模未知
 12. 2. 3  補(bǔ)充結(jié)果
 12. 3  同步器算法
 12. 3. 1  簡(jiǎn)單同步器
 12. 3. 2  a. B和r同步器
 12. 4  應(yīng)用：廣度優(yōu)先搜索
 12. 4. 1  同步BFS算法
 12. 4. 2  與同步器組合
 12. 4. 3  異步BFS算法
 12. 5  Archimedean假設(shè)
 習(xí)題
 第三部分  容  錯(cuò)
 第13章  分布式系統(tǒng)中的容錯(cuò)
 13. 1  利用容錯(cuò)算法的原因
 13. 2  健壯算法
 13. 2. 1  故障模型
 13. 2. 2  判定問(wèn)題
 13. 2. 3  第14章到第16章綜述
 13. 2. 4  本書中沒(méi)有涉及的主題
 13. 3  穩(wěn)定算法
 第14章  異步系統(tǒng)中的容錯(cuò)
 14. 1  一致性的不可能性
 14. 1. 1  表示. 定義及基本結(jié)果
 14. 1. 2  不可能性證明
 14. 1. 3  討論
 14. 2  初始死進(jìn)程
 14. 3  確定可實(shí)現(xiàn)實(shí)例
 14. 3. 1  可解問(wèn)題：重命名
 14. 3. 2  擴(kuò)展的不可能性結(jié)果
 14. 4  概率一致性算法
 14. 4. 1  損毀-健壯一致協(xié)議
 14. 4. 2  Byzantine-健壯一致性協(xié)議
 14. 5  弱終止性
 習(xí)題
 第15章  同步系統(tǒng)中的容錯(cuò)
 15. 1  同步判定協(xié)議
 15. 1. 1  彈性界限
 15. 1. 2  Byzantine廣播算法
 15. 1. 3  多項(xiàng)式級(jí)的廣播算法
 15. 2  鑒別協(xié)議
 15. 2. 1  高度彈性的協(xié)議
 15. 2. 2  數(shù)字簽名的實(shí)現(xiàn)
 15. 2. 3  ElGamal簽名模式
 15. 2. 4  RSA簽名模式
 15. 2. 5  Fiat-Shamir簽名模式
 15. 2. 6  概述和討論
 15. 3  時(shí)鐘同步
 15. 3. 1  讀取遠(yuǎn)程時(shí)鐘
 15. 3. 2  分布式時(shí)鐘同步
 15. 3. 3  輪模型的實(shí)現(xiàn)
 習(xí)題
 第16章  故障檢測(cè)
 16. 1  模型和定義
 16. 1. 1  四種基本檢測(cè)器類型
 16. 1. 2  故障檢測(cè)器的用途和缺陷
 16. 2  用弱精確檢測(cè)器解一致性問(wèn)題
 16. 3  最終弱精確檢測(cè)器
 16. 3. 1  彈性上界
 16. 3. 2  一致算法
 16. 4  故障檢測(cè)器的實(shí)現(xiàn)
 16. 4. 1  同步系統(tǒng)：完美檢測(cè)
 16. 4. 2  部分同步系統(tǒng)：最終完美檢測(cè)
 16. 4. 3  小結(jié)
 習(xí)題
 第17章  穩(wěn)定性
 17. 1  引言
 17. 1. 1  定義
 17. 1. 2  穩(wěn)定系統(tǒng)中的通信
 17. 1. 3  例子：Dijjstra令牌環(huán)
 17. 2  圖論算法
 17. 2. 1  環(huán)定向
 17. 2. 2  最大匹配
 17. 2. 3  選舉和生成樹(shù)構(gòu)造
 17. 3  穩(wěn)定方法學(xué)
 17. 3. 1  協(xié)議組合
 17. 3. 2  計(jì)算最小路徑
 17. 3. 3  結(jié)論和討論
 習(xí)題
 第四部分  附  錄
 附錄A  偽代碼使用約定
 附錄B  圖和網(wǎng)絡(luò)
 參考文獻(xiàn)
 主題詞索引