分佈式算法精髓

互聯網是一個分佈式系統，無線通信、雲計算或並行計算、多核系統、移動網絡也是如此。蟻群、大腦甚至人類社會都可以被建模為分佈式系統。本書強調這些分佈式系統同涉及的主題和技術，特別是強調分佈式系統設計中的一些基本問題，涵蓋通信、協調、容錯性、本地性、並行性、打破對稱性、同步化、不確定性等。

譯者序
前言
第1章 頂點著色
1.1 問題和模型
1.2 著色樹
1.3 本章注釋
1.4 參考文獻

第2章 樹演算法
2.1 廣播
2.2 融合廣播
2.3 廣度優先搜尋樹的構建
2.4 小生成樹的構建
2.5 本章注釋
2.6 參考文獻

第3章 領導人選舉
3.1 匿名領導人選舉
3.2 非同步環
3.3 下界
3.4 同步環
3.5 本章注釋
3.6 參考文獻

第4章 分散式排序
4.1 陣列和網格
4.2 排序網路
4.3 計數網路
4.4 本章注釋
4.5 參考文獻

第5章 共用記憶體
5.1 模型
5.2 互斥
5.3 存儲和收集
5.4 分離器
5.5 二分離樹
5.6 分離器矩陣
5.7 本章注釋
5.8 參考文獻

第6章 共用物件
6.1 集中式解決方案
6.2 Arrow演算法
6.3 Ivy演算法
6.4 本章注釋
6.5 參考文獻

第7章 極大獨立集
7.1 MIS
7.2 原始的快速MIS
7.3 快速MIS v2
7.4 應用
7.5 本章注釋
7.6 參考文獻

第8章 本地下界
8.1 模型
8.2 本地性
8.3 鄰域圖
8.4 本章注釋
8.5 參考文獻

第9章 全域問題
9.1 直徑和APSP
9.2 下界圖
9.3 通信複雜度
9.4 分散式複雜度理論
9.5 本章注釋
9.6 參考文獻

第10章 同步
10.1 基礎知識
10.2 本地同步器α
10.3 全域同步器β
10.4 混合同步器γ
10.5 網路磁碟分割
10.6 時鐘同步
10.7 本章注釋
10.8 參考文獻

第11章 穩定性
11.1 自穩定性
11.2 不錯穩定化
11.3 本章注釋
11.4 參考文獻

第12章 社交網路
12.1 小世界網路
12.2 傳播研究
12.3 本章注釋
12.4 參考文獻

第13章 無線協議
13.1 基礎知識
13.2 非統一的初始化
13.3 使用碰撞檢測的統一初始化
13.4 無碰撞檢測的統一初始化
13.5 領導人選舉
13.6 使用碰撞檢測的快速領導人選舉
13.7 下界
13.8 統一非同步喚醒
13.9 有用的公式
13.10 本章注釋
13.11 參考文獻

第14章 標記方案
14.1 鄰接關係
14.2 有根樹
14.3 道路網路
14.4 本章注釋
14.5 參考文獻

第15章 練習

羅傑·沃滕霍弗（Roger Wattenhofer）博士，蘇黎世聯邦理工學院資訊技術和電氣工程系教授。之前曾任職於微軟研究院、布朗大學和麥考瑞大學。他的研究興趣是演算法和系統，涉及分散式系統、定位系統、容錯分散式系統、高效網路演算法和比特幣等。他已發表學術論文300多篇，曾獲得包括“分散式運算創新獎”在內的眾多獎項。除本書外，他還著有Blockchain Science: Distributed Ledger Technology（2017）一書。
 


譯者簡介


 
黃智瀕  
電腦系統結構博士，北京郵電大學電腦學院講師。長期從事機器學習、超大規模平行計算、GPU加速計算以及三維電腦視覺和深度學習架構方面的研究。