掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
分布式算法(典藏版) 版權信息
- ISBN：9787111724247
- 條形碼：9787111724247 ; 978-7-111-72424-7
- 裝幀：平裝-膠訂
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
分布式算法(典藏版) 本書特色
涵蓋同步模型、異步模型和部分同步模型，為設計、實現和分析分布式算法提供藍圖
分布式算法(典藏版) 內容簡介
本書對分布式算法進行了全面介紹，包括同步模型、異步模型和部分同步模型，針對這些模型討論互斥性、一致性和通信問題，為設計、實現和分析分布式算法提供了藍圖。本書對分布式算法領域的許多經典問題給出了多種解決算法或者不可能性結果，絕大部分的算法附有詳細的證明過程，并且有jing確的復雜度衡量。本書還配有大量習題，并在每章后列出了詳細的參考文獻。本書可作為高等院校計算機專業的研究生教材，尤其適合對計算機理論或體系結構感興趣的學生學習，還適合分布式領域的設計人員和研究人員參考。
分布式算法(典藏版) 目錄
目 錄
Distributed Algorithms
譯者序
前言
第1章 引言 1
1.1 相關主題 1
1.2 我們的觀點 2
1.3 本書內容綜述 4
1.4 參考文獻注釋 7
1.5 標記 8
部分 同步網絡算法
第2章 建模I：同步網絡模型 10
2.1 同步網絡系統 10
2.2 故障 11
2.3 輸入和輸出 11
2.4 運行 12
2.5 證明方法 12
2.6 復雜度度量 12
2.7 隨機化 13
2.8 參考文獻注釋 13
第3章 同步環中的領導者選擇 14
3.1 問題 14
3.2 相同進程的不可能性結果 15
3.3 基本算法 15
3.4 通信復雜度為O (nlogn）的算法 17
3.5 非基于比較的算法 20
3.5.1 時間片算法 20
3.5.2 變速算法 20
3.6 基于比較的算法的下界 22
3.7 非基于比較的算法的下界* 26
3.8 參考文獻注釋 27
3.9 習題 27
第4章 一般同步網絡中的算法 29
4.1 一般網絡中的領導者選舉 29
4.1.1 問題 29
4.1.2 簡單的洪泛算法 29
4.1.3 降低通信復雜度 31
4.2 廣度優先搜索 32
4.2.1 問題 33
4.2.2 基本的廣度優先搜索算法 33
4.2.3 應用 34
4.3 短路徑 35
4.4 小生成樹 36
4.4.1 問題 36
4.4.2 基本定理 36
4.4.3 算法 38
4.5 獨立集 40
4.5.1 問題 40
4.5.2 隨機化算法 41
4.5.3 分析* 42
4.6 參考文獻注釋 44
4.7 習題 44
第5章 鏈路故障時的分布式
一致性 46
5.1 協同攻擊問題—確定性版本 46
5.2 協同攻擊問題—隨機化版本 48
5.2.1 形式化模型 49
5.2.2 算法 49
5.2.3 不一致的下限 52
5.3 參考文獻注釋 54
5.4 習題 54
第6章 進程故障下的分布式
一致性 56
6.1 問題 57
6.2 針對停止故障的算法 58
6.2.1 基本算法 58
6.2.2 減少通信 60
6.2.3 指數信息收集算法 61
6.2.4 帶鑒別的Byzantine一致性 66
6.3 針對Byzantine故障的算法 66
6.3.1 舉例 67
6.3.2 Byzantine一致性問題的EIG
算法 68
6.3.3 使用二元Byzantine一致性的
一般Byzantine一致性問題 71
6.3.4 減少通信開銷 72
6.4 Byzantine一致性問題中進程的
個數 75
6.5 一般圖中的Byzantine一致性
問題 78
6.6 弱Byzantine一致性 81
6.7 有停止故障時的輪數 82
6.8 參考文獻注釋 88
6.9 習題 89
第7章 更多的一致性問題 93
7.1 k一致性問題 93
7.1.1 問題 93
7.1.2 算法 94
7.1.3 下界* 95
7.2 近似一致性 103
7.3 提交問題 106
7.3.1 問題 106
7.3.2 兩階段提交 107
7.3.3 三階段提交 108
7.3.4 消息數的下界 110
7.4 參考文獻注釋 112
7.5 習題 112
第二部分 異步算法
第8章 建模II：異步系統模型 116
8.1 輸入/輸出自動機 116
8.2 自動機的操作 120
8.2.1 合成 120
8.2.2 隱藏 123
8.3 公平性 123
8.4 問題的輸入和輸出 126
8.5 屬性與證明方法 126
8.5.1 不變式斷言 126
8.5.2 軌跡屬性 126
8.5.3 安全與活性屬性 127
8.5.4 合成推理 129
8.5.5 層次化證明 131
8.6 復雜度衡量 133
8.7 不可區分的運行 134
8.8 隨機化 134
8.9 參考文獻注釋 134
8.10 習題 135
第二部分A?異步共享存儲器算法
第9章 建模III：異步共享存儲器
模型 138
9.1 共享存儲器系統 138
9.2 環境模型 140
9.3 不可區分狀態 141
9.4 共享變量類型 142
9.5 復雜度衡量 145
9.6 故障 146
9.7 隨機化 146
9.8 參考文獻注釋 146
9.9 習題 146
第10章 互斥 148
10.1 異步共享存儲器模型 148
10.2 問題 150
10.3 Dijkstra的互斥算法 153
10.3.1 算法 153
10.3.2 正確性證明 156
10.3.3 互斥條件的一個斷言式
證明 158
10.3.4 運行時間 159
10.4 互斥算法的更強條件 160
10.5 鎖定權互斥算法 162
10.5.1 雙進程算法 162
10.5.2 n進程算法 165
10.5.3 錦標賽算法 169
10.6 使用單寫者共享寄存器的算法 172
10.7 Bakery算法 174
10.8 寄存器數量的下界 176
10.8.1 基本事實 177
10.8.2 單寫者共享變量 177
10.8.3 多寫者共享變量 178
10.9 使用讀–改–寫共享變量的
互斥 182
10.9.1 基本問題 182
10.9.2 有界繞過次數 183
10.9.3 鎖定權 188
10.9.4 模擬證明 190
10.10 參考文獻注釋 193
10.11 習題 193
第11章 資源分配 197
11.1?問題 197
11.1.1 顯式資源規格說明和互斥規格說明 197
11.1.2 資源分配問題 198
11.1.3 哲學家用餐問題 199
11.1.4 解法的受限形式 200
11.2 對稱哲學家用餐算法的
不存在性 200
11.3 右–左哲學家用餐算法 202
11.3.1 等待鏈 202
11.3.2 基本算法 203
11.3.3 擴展 205
11.4 隨機哲學家用餐算法* 208
11.4.1 算法* 208
11.4.2 正確性* 210
11.5 參考文獻注釋 216
11.6 習題 216
第12章 一致性 218
12.1?問題 218
12.2 使用讀/寫共享存儲器的一致性
問題 220
12.2.1 限制 221
12.2.2 術語 221
12.2.3 雙價初始化 222
12.2.4 無等待終止性的不可能性 222
12.2.5 單故障終止性的不可能性
結果 224
12.3 讀/改/寫共享存儲器上的
一致性問題 227
12.4 其他共享存儲器類型 227
12.5 異步共享存儲器系統中的可
計算性* 227
12.6 參考文獻注釋 229
12.7 習題 229
第13章 原子對象 232
13.1 定義和基本結論 232
13.1.1 原子對象的定義 233
13.1.2 規范無等待原子對象
自動機 238
13.1.3 原子對象的合成 240
13.1.4 原子對象和共享變量 240
13.1.5 顯示原子性的一個充分
條件 245
13.2 用讀/寫變量實現讀–改–寫
原子對象 246
13.3 共享存儲器的原子快照 247
13.3.1 問題 247
13.3.2 帶無界變量的一個算法 248
13.3.3 帶有界變量的一個算法* 251
13.4 讀/寫原子對象 254
13.4.1 問題 254
13.4.2 證明原子性的其他引理 255
13.4.3 帶無界變量的一個算法 256
13.4.4 兩個寫者的有界算法 259
13.4.5 使用快照的算法 263
13.5 參考文獻注釋 264
13.6 習題 265
第二部分B 異步網絡算法
第14章 建模IV：異步網絡模型 268
14.1 發送/接收系統 268
14.1.1 進程 268
14.1.2 發送/接收通道 269
14.1.3 異步發送/接收系統 272
14.1.4 使用可靠FIFO通道的發送/
接收系統的屬性 272
14.1.5 復雜度度量 273
14.2 廣播系統 274
14.2.1 進程 274
14.2.2 廣播通道 274
14.2.3 異步廣播系統 275
14.2.4 采用可靠廣播通道的廣播系統的屬性 275
14.2.5 復雜度度量 275
14.3 多播系統 275
14.3.1 進程 276
14.3.2 多播通道 276
14.3.3 異步多播系統 276
14.4 參考文獻注釋 277
14.5 習題 277
第15章 基本異步網絡算法 279
15.1 環中的領導者選舉 279
15.1.1 LCR算法 279
15.1.2 HS算法 283
15.1.3 PetersonLeader算法 283
15.1.4 通信復雜度的下界 286
15.2 任意網絡中的領導者選舉 291
15.3 生成樹的構造、廣播和斂播 292
15.4 廣度優先搜索和短路徑 295
15.5 小生成樹 300
15.5.1 問題描述 301
15.5.2 同步算法：回顧 301
15.5.3 GHS算法：概要 302
15.5.4 更詳細的算法 303
15.5.5 特殊消息 305
15.5.6 復雜度分析 306
15.5.7 GHS算法的正確性證明 307
15.5.8 簡單“同步”策略 308
15.5.9 應用到領導者選舉算法中 308
15.6 參考文獻注釋 309
15.7 習題 309
第16章 同步器 313
16.1 問題 313
16.2 局部同步器 315
16.3 安全同步器 319
16.3.1 前端自動機 320
16.3.2 通道自動機 321
16.3.3 安全同步器的任務 321
16.3.4 正確性 322
16.4 安全同步器的實現 322
16.4.1 同步器Alpha 322
16.4.2 同步器Beta 323
16.4.3 同步器Gamma 323
16.5 應用 327
16.5.1 領導者選舉 327
16.5.2 廣度優先搜索 327
16.5.3 短路徑 328
16.5.4 廣播與確認 328
16.5.5 獨立集 328
16.6 時間下界 328
16.7 參考文獻注釋 331
16.8 習題 331
第17章 共享存儲器與網絡 333
17.1 從異步共享存儲器模型到異步
網絡模型的轉換 333
17.1.1 問題 333
17.1.2 無故障時的策略 334
17.1.3 容忍進程故障的算法 339
17.1.4 對于n/2故障的不可能性
結果 342
17.2 從異步網絡模型到異步共享存儲器模型的轉換 343
17.2.1 發送/接收系統 344
17.2.2 廣播系統 345
17.2.3 異步網絡中一致性的
不可能性 346
17.3 參考文獻注釋 346
17.4 習題 346
第18章
Distributed Algorithms
譯者序
前言
第1章 引言 1
1.1 相關主題 1
1.2 我們的觀點 2
1.3 本書內容綜述 4
1.4 參考文獻注釋 7
1.5 標記 8
部分 同步網絡算法
第2章 建模I：同步網絡模型 10
2.1 同步網絡系統 10
2.2 故障 11
2.3 輸入和輸出 11
2.4 運行 12
2.5 證明方法 12
2.6 復雜度度量 12
2.7 隨機化 13
2.8 參考文獻注釋 13
第3章 同步環中的領導者選擇 14
3.1 問題 14
3.2 相同進程的不可能性結果 15
3.3 基本算法 15
3.4 通信復雜度為O (nlogn）的算法 17
3.5 非基于比較的算法 20
3.5.1 時間片算法 20
3.5.2 變速算法 20
3.6 基于比較的算法的下界 22
3.7 非基于比較的算法的下界* 26
3.8 參考文獻注釋 27
3.9 習題 27
第4章 一般同步網絡中的算法 29
4.1 一般網絡中的領導者選舉 29
4.1.1 問題 29
4.1.2 簡單的洪泛算法 29
4.1.3 降低通信復雜度 31
4.2 廣度優先搜索 32
4.2.1 問題 33
4.2.2 基本的廣度優先搜索算法 33
4.2.3 應用 34
4.3 短路徑 35
4.4 小生成樹 36
4.4.1 問題 36
4.4.2 基本定理 36
4.4.3 算法 38
4.5 獨立集 40
4.5.1 問題 40
4.5.2 隨機化算法 41
4.5.3 分析* 42
4.6 參考文獻注釋 44
4.7 習題 44
第5章 鏈路故障時的分布式
一致性 46
5.1 協同攻擊問題—確定性版本 46
5.2 協同攻擊問題—隨機化版本 48
5.2.1 形式化模型 49
5.2.2 算法 49
5.2.3 不一致的下限 52
5.3 參考文獻注釋 54
5.4 習題 54
第6章 進程故障下的分布式
一致性 56
6.1 問題 57
6.2 針對停止故障的算法 58
6.2.1 基本算法 58
6.2.2 減少通信 60
6.2.3 指數信息收集算法 61
6.2.4 帶鑒別的Byzantine一致性 66
6.3 針對Byzantine故障的算法 66
6.3.1 舉例 67
6.3.2 Byzantine一致性問題的EIG
算法 68
6.3.3 使用二元Byzantine一致性的
一般Byzantine一致性問題 71
6.3.4 減少通信開銷 72
6.4 Byzantine一致性問題中進程的
個數 75
6.5 一般圖中的Byzantine一致性
問題 78
6.6 弱Byzantine一致性 81
6.7 有停止故障時的輪數 82
6.8 參考文獻注釋 88
6.9 習題 89
第7章 更多的一致性問題 93
7.1 k一致性問題 93
7.1.1 問題 93
7.1.2 算法 94
7.1.3 下界* 95
7.2 近似一致性 103
7.3 提交問題 106
7.3.1 問題 106
7.3.2 兩階段提交 107
7.3.3 三階段提交 108
7.3.4 消息數的下界 110
7.4 參考文獻注釋 112
7.5 習題 112
第二部分 異步算法
第8章 建模II：異步系統模型 116
8.1 輸入/輸出自動機 116
8.2 自動機的操作 120
8.2.1 合成 120
8.2.2 隱藏 123
8.3 公平性 123
8.4 問題的輸入和輸出 126
8.5 屬性與證明方法 126
8.5.1 不變式斷言 126
8.5.2 軌跡屬性 126
8.5.3 安全與活性屬性 127
8.5.4 合成推理 129
8.5.5 層次化證明 131
8.6 復雜度衡量 133
8.7 不可區分的運行 134
8.8 隨機化 134
8.9 參考文獻注釋 134
8.10 習題 135
第二部分A?異步共享存儲器算法
第9章 建模III：異步共享存儲器
模型 138
9.1 共享存儲器系統 138
9.2 環境模型 140
9.3 不可區分狀態 141
9.4 共享變量類型 142
9.5 復雜度衡量 145
9.6 故障 146
9.7 隨機化 146
9.8 參考文獻注釋 146
9.9 習題 146
第10章 互斥 148
10.1 異步共享存儲器模型 148
10.2 問題 150
10.3 Dijkstra的互斥算法 153
10.3.1 算法 153
10.3.2 正確性證明 156
10.3.3 互斥條件的一個斷言式
證明 158
10.3.4 運行時間 159
10.4 互斥算法的更強條件 160
10.5 鎖定權互斥算法 162
10.5.1 雙進程算法 162
10.5.2 n進程算法 165
10.5.3 錦標賽算法 169
10.6 使用單寫者共享寄存器的算法 172
10.7 Bakery算法 174
10.8 寄存器數量的下界 176
10.8.1 基本事實 177
10.8.2 單寫者共享變量 177
10.8.3 多寫者共享變量 178
10.9 使用讀–改–寫共享變量的
互斥 182
10.9.1 基本問題 182
10.9.2 有界繞過次數 183
10.9.3 鎖定權 188
10.9.4 模擬證明 190
10.10 參考文獻注釋 193
10.11 習題 193
第11章 資源分配 197
11.1?問題 197
11.1.1 顯式資源規格說明和互斥規格說明 197
11.1.2 資源分配問題 198
11.1.3 哲學家用餐問題 199
11.1.4 解法的受限形式 200
11.2 對稱哲學家用餐算法的
不存在性 200
11.3 右–左哲學家用餐算法 202
11.3.1 等待鏈 202
11.3.2 基本算法 203
11.3.3 擴展 205
11.4 隨機哲學家用餐算法* 208
11.4.1 算法* 208
11.4.2 正確性* 210
11.5 參考文獻注釋 216
11.6 習題 216
第12章 一致性 218
12.1?問題 218
12.2 使用讀/寫共享存儲器的一致性
問題 220
12.2.1 限制 221
12.2.2 術語 221
12.2.3 雙價初始化 222
12.2.4 無等待終止性的不可能性 222
12.2.5 單故障終止性的不可能性
結果 224
12.3 讀/改/寫共享存儲器上的
一致性問題 227
12.4 其他共享存儲器類型 227
12.5 異步共享存儲器系統中的可
計算性* 227
12.6 參考文獻注釋 229
12.7 習題 229
第13章 原子對象 232
13.1 定義和基本結論 232
13.1.1 原子對象的定義 233
13.1.2 規范無等待原子對象
自動機 238
13.1.3 原子對象的合成 240
13.1.4 原子對象和共享變量 240
13.1.5 顯示原子性的一個充分
條件 245
13.2 用讀/寫變量實現讀–改–寫
原子對象 246
13.3 共享存儲器的原子快照 247
13.3.1 問題 247
13.3.2 帶無界變量的一個算法 248
13.3.3 帶有界變量的一個算法* 251
13.4 讀/寫原子對象 254
13.4.1 問題 254
13.4.2 證明原子性的其他引理 255
13.4.3 帶無界變量的一個算法 256
13.4.4 兩個寫者的有界算法 259
13.4.5 使用快照的算法 263
13.5 參考文獻注釋 264
13.6 習題 265
第二部分B 異步網絡算法
第14章 建模IV：異步網絡模型 268
14.1 發送/接收系統 268
14.1.1 進程 268
14.1.2 發送/接收通道 269
14.1.3 異步發送/接收系統 272
14.1.4 使用可靠FIFO通道的發送/
接收系統的屬性 272
14.1.5 復雜度度量 273
14.2 廣播系統 274
14.2.1 進程 274
14.2.2 廣播通道 274
14.2.3 異步廣播系統 275
14.2.4 采用可靠廣播通道的廣播系統的屬性 275
14.2.5 復雜度度量 275
14.3 多播系統 275
14.3.1 進程 276
14.3.2 多播通道 276
14.3.3 異步多播系統 276
14.4 參考文獻注釋 277
14.5 習題 277
第15章 基本異步網絡算法 279
15.1 環中的領導者選舉 279
15.1.1 LCR算法 279
15.1.2 HS算法 283
15.1.3 PetersonLeader算法 283
15.1.4 通信復雜度的下界 286
15.2 任意網絡中的領導者選舉 291
15.3 生成樹的構造、廣播和斂播 292
15.4 廣度優先搜索和短路徑 295
15.5 小生成樹 300
15.5.1 問題描述 301
15.5.2 同步算法：回顧 301
15.5.3 GHS算法：概要 302
15.5.4 更詳細的算法 303
15.5.5 特殊消息 305
15.5.6 復雜度分析 306
15.5.7 GHS算法的正確性證明 307
15.5.8 簡單“同步”策略 308
15.5.9 應用到領導者選舉算法中 308
15.6 參考文獻注釋 309
15.7 習題 309
第16章 同步器 313
16.1 問題 313
16.2 局部同步器 315
16.3 安全同步器 319
16.3.1 前端自動機 320
16.3.2 通道自動機 321
16.3.3 安全同步器的任務 321
16.3.4 正確性 322
16.4 安全同步器的實現 322
16.4.1 同步器Alpha 322
16.4.2 同步器Beta 323
16.4.3 同步器Gamma 323
16.5 應用 327
16.5.1 領導者選舉 327
16.5.2 廣度優先搜索 327
16.5.3 短路徑 328
16.5.4 廣播與確認 328
16.5.5 獨立集 328
16.6 時間下界 328
16.7 參考文獻注釋 331
16.8 習題 331
第17章 共享存儲器與網絡 333
17.1 從異步共享存儲器模型到異步
網絡模型的轉換 333
17.1.1 問題 333
17.1.2 無故障時的策略 334
17.1.3 容忍進程故障的算法 339
17.1.4 對于n/2故障的不可能性
結果 342
17.2 從異步網絡模型到異步共享存儲器模型的轉換 343
17.2.1 發送/接收系統 344
17.2.2 廣播系統 345
17.2.3 異步網絡中一致性的
不可能性 346
17.3 參考文獻注釋 346
17.4 習題 346
第18章
展開全部
分布式算法(典藏版) 作者簡介
南希·A. 林奇（Nancy A. Lynch） 麻省理工學院電子工程和計算機科學系教授，領導麻省理工學院的分布式系統理論研究組，在分布式算法和不可能解以及分布式系統的形式化建模和證明方面編寫了大量著作。
書友推薦
- >
新文學天穹兩巨星--魯迅與胡適/紅燭學術叢書(紅燭學術叢書)
- >
詩經-先民的歌唱
- >
名家帶你讀魯迅:故事新編
- >
伊索寓言-世界文學名著典藏-全譯本
- >
我從未如此眷戀人間
- >
隨園食單
- >
巴金－再思錄
- >
企鵝口袋書系列·偉大的思想20:論自然選擇(英漢雙語)
本類暢銷
