分布式系統(tǒng)設計

作者簡介
譯者序
前言
第1章 概論 
1.1 推動因素 
1.2 基本計算機組成 
1.3 分布式系統(tǒng)的定義 
1.4 我們的模型 
1.5 互連網(wǎng)絡 
1.6 應用與標準 
1.7 范圍 
1.8 參考資料來源 
參考文獻 
習題 
第2章 分布式程序設計語言 
2.1 分布式程序設計支持的需求 
2.2 并行/分布式程序設計語言概述 
2.3 并行性的表示 
2.4 進程通信與同步 
2.5 遠程過程調(diào)用 
2.6 健壯性 
參考文獻 
習題 
第3章 分布式系統(tǒng)設計的形式方法 
3.1 模型的介紹 
3.1.1 狀態(tài)機模型 
3.1.2 佩特里網(wǎng) 
3.2 因果相關事件 
3.2.1 發(fā)生在先關系 
3.2.2 時空視圖 
3.2.3 交叉視圖 
3.3 全局狀態(tài) 
3.3.1 時空視圖中的全局狀態(tài) 
3.3.2 全局狀態(tài)：一個形式定義 
3.3.3 全局狀態(tài)的"快照" 
3.3.4 一致全局狀態(tài)的充要條件 
3.4 邏輯時鐘 
3.4.1 標量邏輯時鐘 
3.4.2 擴展 
3.4.3 有效實現(xiàn) 
3.4.4 物理時鐘 
3.5 應用 
3.5.1 一個全序應用：分布式互斥 
3.5.2 一個邏輯向量時鐘應用：消息的排序 
3.6 分布式控制算法的分類 
3.7 分布式算法的復雜性 
參考文獻 
習題 
第4章 互斥和選舉算法 
4.1 互斥 
4.2 非基于權標的解決方案 
4.2.1 Lamport算法的簡單擴展 
4.2.2 Ricart和Agrawala的第一個算法 
4.2.3 Maekawa的算法 
4.3 基于權標的解決方案 
4.3.1 Ricart和Agrawala的第二個算法 
4.3.2 一個簡單的基于權標環(huán)的算法 
4.3.3 一個基于權標環(huán)的容錯算法 
4.3.4 基于權標的使用其他邏輯結構的互斥 
4.4 選舉 
4.4.1 Chang和Roberts的算法 
4.4.2 非基于比較的算法 
4.5 投標 
4.6 自穩(wěn)定 
參考文獻 
習題 
第5章 死鎖的預防、避免和檢測 
5.1 死鎖問題 
5.1.1 死鎖發(fā)生的條件 
5.1.2 圖論模型 
5.1.3 處理死鎖的策略 
5.1.4 請求模型 
5.1.5 資源和進程模型 
5.1.6 死鎖條件 
5.2 死鎖預防 
5.3 一個死鎖預防的例子：分布式數(shù)據(jù)庫系統(tǒng) 
5.4 死鎖避免 
5.5 一個死鎖避免的例子：多機器人的靈活裝配單元 
5.6 死鎖檢測和恢復 
5.6.1 集中式方法 
5.6.2 分布式方法 
5.6.3 等級式方法 
5.7 死鎖檢測和恢復的例子 
5.7.1 AND模型下的Chandy，Misra和Hass算法 
5.7.2 AND模型下的Mitchell和Merritt算法 
5.7.3 OR模型下的Chandy，Misra和Hass算法 
參考文獻 
習題 
第6章 分布式路由算法 
6.1 導論 
6.1.1 拓撲 
6.1.2 交換 
6.1.3 通信類型 
6.1.4 路由 
6.1.5 路由函數(shù) 
6.2 一般類型的最短路徑路由 
6.2.1 Dijkstra集中式算法 
6.2.2 Ford的分布式算法 
6.2.3 ARPAnet的路由策略 
6.3 特殊類型網(wǎng)絡中的單播 
6.3.1 雙向環(huán) 
6.3.2 網(wǎng)格和圓環(huán) 
6.3.3 超立方 
6.4 特殊類型網(wǎng)絡中的廣播 
6.4.1 環(huán) 
6.4.2 2維網(wǎng)格和圓環(huán) 
6.4.3 超立方 
6.5 特殊類型網(wǎng)絡中的組播 
6.5.1 一般方法 
6.5.2 基于路徑的方法 
6.5.3 基于樹的方法 
參考文獻 
習題 
第7章 自適應、無死鎖和容錯路由 
7.1 虛信道和虛網(wǎng)絡 
7.2 完全自適應和無死鎖路由 
7.2.1 虛信道類 
7.2.2 逃逸信道 
7.3 部分自適應和無死鎖路由 
7.4 容錯單播：一般方法 
7.5 2維網(wǎng)格和圓環(huán)中的容錯單播 
7.5.1 基于局部信息的路由 
7.5.2 基于有限全局信息的路由 
7.5.3 基于其他故障模型的路由 
7.6 超立方中的容錯單播 
7.6.1 基于局部信息的模型 
7.6.2 基于有限全局信息的模型：安全等級 
7.6.3 基于擴展安全等級模型的路由：安全向量 
7.7 容錯廣播 
7.7.1 一般方法 
7.7.2 使用全局信息的廣播 
7.7.3 使用安全等級進行廣播 
7.8 容錯組播 
7.8.1 一般方法 
7.8.2 基于路徑的路由 
7.8.3 使用安全等級在超立方中進行組播 
參考文獻 
習題 
第8章 分布式系統(tǒng)的可靠性 
8.1 基本模型 
8.2 容錯系統(tǒng)設計的構件模塊 
8.2.1 穩(wěn)定存儲器 
8.2.2 故障-停止處理器 
8.2.3 原子操作 
8.3 節(jié)點故障的處理 
8.3.1 向后式恢復 
8.3.2 前卷式恢復 
8.4 向后恢復中的問題 
8.4.1 檢查點的存儲 
8.4.2 檢查點方法 
8.5 處理拜占庭式故障 
8.5.1 同步系統(tǒng)中的一致協(xié)議 
8.5.2 對一個發(fā)送者的一致 
8.5.3 對多個發(fā)送者的一致 
8.5.4 不同模型下的一致 
8.5.5 對驗證消息的一致 
8.6 處理通信故障 
8.7 處理軟件故障 
參考文獻 
習題 
第9章 靜態(tài)負載分配 
9.1 負載分配的分類 
9.2 靜態(tài)負載分配 
9.2.1 處理器互連 
9.2.2 任務劃分 
9.2.3 任務分配 
9.3 不同調(diào)度模型概述 
9.4 基于任務優(yōu)先圖的任務調(diào)度 
9.5 案例學習：兩種最優(yōu)調(diào)度算法 
9.6 基于任務相互關系圖的任務調(diào)度 
9.7 案例學習：域劃分 
9.8 使用其他模型和目標的調(diào)度 
9.8.1 網(wǎng)絡流量技術：有不同處理器能力的任務相互關系圖 
9.8.2 速率單調(diào)優(yōu)先調(diào)度和期限驅動調(diào)度：帶實時限制的定期任務 
9.8.3 通過任務復制實現(xiàn)故障安全調(diào)度：樹結構的任務優(yōu)先圖 
9.9 未來的研究方向 
參考文獻 
習題 
第10章 動態(tài)負載分配 
10.1 動態(tài)負載分配 
10.1.1 動態(tài)負載分配的組成要素 
10.1.2 動態(tài)負載分配算法 
10.2 負載平衡設計決策 
10.2.1 靜態(tài)算法對動態(tài)算法 
10.2.2 多樣化信息策略 
10.2.3 集中控制算法和分散控制算法 
10.2.4 移植啟動策略 
10.2.5 資源復制 
10.2.6 進程分類 
10.2.7 操作系統(tǒng)和獨立任務啟動策略 
10.2.8 開環(huán)控制和閉環(huán)控制 
10.2.9 使用硬件和使用軟件 
10.3 移植策略：發(fā)送者啟動和接收者啟動 
10.4 負載平衡使用的參數(shù) 
10.4.1 系統(tǒng)大小 
10.4.2 系統(tǒng)負載 
10.4.3 系統(tǒng)交通強度 
10.4.4 移植閾值 
10.4.5 任務大小 
10.4.6 管理成本 
10.4.7 響應時間 
10.4.8 負載平衡視界 
10.4.9 資源要求 
10.5 其他相關因素 
10.5.1 編碼文件和數(shù)據(jù)文件 
10.5.2 系統(tǒng)穩(wěn)定性 
10.5.3 系統(tǒng)體系結構 
10.6 負載平衡算法實例 
10.6.1 直接算法 
10.6.2 最近鄰居算法：擴散 
10.6.3 最近鄰居算法：梯度 
10.6.4 最近鄰居算法：維交換 
10.7 案例學習：超立方體多計算機上的負載平衡 
10.8 未來的研究方向 
參考文獻 
習題 
第11章 分布式數(shù)據(jù)管理 
11.1 基本概念 
11.2 可串行性理論 
11.3 并發(fā)控制 
11.3.1 基于鎖的并發(fā)控制 
11.3.2 基于時戳的并發(fā)控制 
11.3.3 樂觀的并發(fā)控制 
11.4 復制和一致性管理 
11.4.1 主站點方法 
11.4.2 活動復制 
11.4.3 選舉協(xié)議 
11.4.4 網(wǎng)絡劃分的樂觀方法：版本號向量 
11.4.5 網(wǎng)絡分割的悲觀方法：動態(tài)選舉 
11.5 分布式可靠性協(xié)議 
參考文獻 
習題 
第12章 分布式系統(tǒng)的應用 
12.1 分布式操作系統(tǒng) 
12.1.1 服務器結構 
12.1.2 八種服務類型 
12.1.3 基于微內(nèi)核的系統(tǒng) 
12.2 分布式文件系統(tǒng) 
12.2.1 文件存取模型 
12.2.2 文件共享語義 
12.2.3 文件系統(tǒng)合并 
12.2.4 保護 
12.2.5 命名和名字服務 
12.2.6 加密 
12.2.7 緩存 
12.3 分布式共享存儲器 
12.3.1 存儲器相關性問題 
12.3.2 Stumm和Zhou的分類 
12.3.3 Li和Hudak的分類 
12.4 分布式數(shù)據(jù)庫系統(tǒng) 
12.5 異構型處理 
12.6 分布式系統(tǒng)的未來研究方向 
參考文獻 
習題 
附錄 DCDL中的通用符號列表 
索引