分布式算法導論（原書第2版）

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