分佈式算法精髓 Mastering Distributed Algorithms

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

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

譯者序
前言
第1章 頂點著色1
1.1 問題和模型1
1.2 著色樹3
1.3 本章註釋8
1.4 參考文獻9
第2章 樹算法13
2.1 廣播13
2.2 融合廣播15
2.3 廣度優先搜索樹的構建15
2.4 最小生成樹的構建17
2.5 本章註釋20
2.6 參考文獻20
第3章 領導人選舉23
3.1 匿名領導人選舉23
3.2 異步環24
3.3 下界27
3.4 同步環29
3.5 本章註釋30
3.6 參考文獻31
第4章 分佈式排序33
4.1 數組和網格33
4.2 排序網絡36
4.3 計數網絡40
4.4 本章註釋44
4.5 參考文獻45
第5章 共享內存47
5.1 模型47
5.2 互斥48
5.3 存儲和收集51
5.4 分離器53
5.5 二叉分離樹54
5.6 分離器矩陣56
5.7 本章註釋57
5.8 參考文獻57
第6章 共享對象59
6.1 集中式解決方案59
6.2 Arrow算法60
6.3 Ivy算法65
6.4 本章註釋69
6.5 參考文獻69
第7章 極大獨立集73
7.1 MIS73
7.2 原始的快速MIS75
7.3 快速MIS v278
7.4 應用83
7.5 本章註釋84
7.6 參考文獻85
第8章 本地下界87
8.1 模型87
8.2 本地性87
8.3 鄰域圖90
8.4 本章註釋94
8.5 參考文獻95
第9章 全局問題97
9.1 直徑和APSP97
9.2 下界圖100
9.3 通信複雜度102
9.4 分佈式複雜度理論108
9.5 本章註釋109
9.6 參考文獻110
第10章 同步113
10.1 基礎知識113
10.2 本地同步器α114
10.3 全局同步器β115
10.4 混合同步器γ116
10.5 網絡分區118
10.6 時鐘同步120
10.7 本章註釋123
10.8 參考文獻124
第11章 穩定性127
11.1 自穩定性127
11.2 高級穩定化132
11.3 本章註釋135
11.4 參考文獻136
第12章 社交網絡137
12.1 小世界網絡137
12.2 傳播研究145
12.3 本章註釋146
12.4 參考文獻146
第13章 無線協議149
13.1 基礎知識149
13.2 非統一的初始化150
13.3 使用碰撞檢測的統一初始化151
13.4 無碰撞檢測的統一初始化153
13.5 領導人選舉154
13.6 使用碰撞檢測的快速領導人選舉155
13.7 下界159
13.8 統一異步喚醒160
13.9 有用的公式161
13.10 本章註釋162
13.11 參考文獻162
第14章 標記方案165
14.1 鄰接關係165
14.2 有根樹167
14.3 道路網絡169
14.4 本章註釋171
14.5 參考文獻172
第15章 練習175