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

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