分布式算法精髓

罗杰·沃滕霍弗（Roger Wattenhofer） 博士，苏黎世联邦理工学院信息技术和电气工程系教授。之前曾任职于微软研究院、布朗大学和麦考瑞大学。他的研究兴趣是算法和系统，涉及分布式系统、定位系统、容错分布式系统、高效网络算法和比特币等。他已发表学术论文300多篇，曾获得包括“分布式计算创新奖”在内的众多奖项。除本书外，他还著有Blockchain Science: Distributed Ledger Technology（2017）一书。 译者简介---黄智濒   计算机系统结构博士，北京邮电大学计算机学院讲师。长期从事机器学习、超大规模并行计算、GPU加速计算以及三维计算机视觉和深度学习架构方面的研究。

译者序<br/>前言<br/>第1章  顶点着色1<br/>  1.1  问题和模型1<br/>  1.2  着色树3<br/>  1.3  本章注释8<br/>  1.4  参考文献9<br/>第2章  树算法13<br/>  2.1  广播13<br/>  2.2  融合广播15<br/>  2.3  广度优先搜索树的构建15<br/>  2.4  最小生成树的构建17<br/>  2.5  本章注释20<br/>  2.6  参考文献20<br/>第3章  领导人选举23<br/>  3.1  匿名领导人选举23<br/>  3.2  异步环24<br/>  3.3  下界27<br/>  3.4  同步环29<br/>  3.5  本章注释30<br/>  3.6  参考文献31<br/>第4章  分布式排序33<br/>  4.1  数组和网格33<br/>  4.2  排序网络36<br/>  4.3  计数网络40<br/>  4.4  本章注释44<br/>  4.5  参考文献45<br/>第5章  共享内存47<br/>  5.1  模型47<br/>  5.2  互斥48<br/>  5.3  存储和收集51<br/>  5.4  分离器53<br/>  5.5  二叉分离树54<br/>  5.6  分离器矩阵56<br/>  5.7  本章注释57<br/>  5.8  参考文献57<br/>第6章  共享对象59<br/>  6.1  集中式解决方案59<br/>  6.2  Arrow算法60<br/>  6.3  Ivy算法65<br/>  6.4  本章注释69<br/>  6.5  参考文献69<br/>第7章  极大独立集73<br/>  7.1  MIS73<br/>  7.2  原始的快速MIS75<br/>  7.3  快速MIS v278<br/>  7.4  应用83<br/>  7.5  本章注释84<br/>  7.6  参考文献85<br/>第8章  本地下界87<br/>  8.1  模型87<br/>  8.2  本地性87<br/>  8.3  邻域图90<br/>  8.4  本章注释94<br/>  8.5  参考文献95<br/>第9章  全局问题97<br/>  9.1  直径和APSP97<br/>  9.2  下界图100<br/>  9.3  通信复杂度102<br/>  9.4  分布式复杂度理论108<br/>  9.5  本章注释109<br/>  9.6  参考文献110<br/>第10章  同步113<br/>  10.1  基础知识113<br/>  10.2  本地同步器α114<br/>  10.3  全局同步器β115<br/>  10.4  混合同步器γ116<br/>  10.5  网络分区118<br/>  10.6  时钟同步120<br/>  10.7  本章注释123<br/>  10.8  参考文献124<br/>第11章  稳定性127<br/>  11.1  自稳定性127<br/>  11.2  不错稳定化132<br/>  11.3  本章注释135<br/>  11.4  参考文献136<br/>第12章  社交网络137<br/>  12.1  小世界网络137<br/>  12.2  传播研究145<br/>  12.3  本章注释146<br/>  12.4  参考文献146<br/>第13章  无线协议149<br/>  13.1  基础知识149<br/>  13.2  非统一的初始化150<br/>  13.3  使用碰撞检测的统一初始化151<br/>  13.4  无碰撞检测的统一初始化153<br/>  13.5  领导人选举154<br/>  13.6  使用碰撞检测的快速领导人选举155<br/>  13.7  下界159<br/>  13.8  统一异步唤醒160<br/>  13.9  有用的公式161<br/>  13.10  本章注释162<br/>  13.11  参考文献162<br/>第14章  标记方案165<br/>  14.1  邻接关系165<br/>  14.2  有根树167<br/>  14.3  道路网络169<br/>  14.4  本章注释171<br/>  14.5  参考文献172<br/>第15章  练习175

互联网是一个分布式系统，无线通信、云计算或并行计算、多核系统、移动网络也是如此。蚁群、大脑甚至人类社会都可以被建模为分布式系统。本书强调这些分布式系统同涉及的主题和技术，特别是强调分布式系统设计中的一些基本问题，涵盖通信、协调、容错性、本地性、并行性、打破对称性、同步化、不确定性等。