分布式计算基础：从理论到实践

“Distributed Computing.pdf”是一本关于分布式计算的英文教程，由Roger Wattenhofer撰写，适用于2016年的春季学期。该书涵盖了分布式计算中的关键概念和技术，包括顶点着色、树算法、领导者选举、分布式排序、共享内存模型、共享对象以及最大独立集等。 在分布式计算中，**顶点着色（Vertex Coloring）**是解决资源分配和冲突避免的问题。第1章介绍了问题的模型，并特别讨论了如何对树进行着色。在树的着色中，每个节点被赋予一种颜色，相邻的节点不能有相同的颜色，以确保无冲突的分配。 **树算法（Tree Algorithms）**是分布式计算中的基础。第2章讲解了广播、收敛传播、最短路径树构建（BFSTreeConstruction）以及最小生成树构造（MSTConstruction）。这些算法在分布式系统中用于信息传播、数据聚合和网络构建。 **领导者选举（Leader Election）**在分布式系统中至关重要，用于确定一个协调节点。第3章分别探讨了匿名领导者选举、异步环和同步环中的选举方法，以及与之相关的下界理论。 **分布式排序（Distributed Sorting）**是数据处理的关键部分。第4章介绍了数组和网格上的排序，以及排序网络和计数网络，这些技术允许在网络中高效地排序大量数据。 **共享内存（Shared Memory）**模型在多线程编程中常见。第5章定义了模型，深入讨论了互斥访问（Mutual Exclusion）问题，以及如何通过分割器（Splitters）实现存储和收集操作，如二进制分割器树和分割器矩阵。 **共享对象（Shared Objects）**是并发编程中的抽象。第6章介绍了集中式解决方案，比如Arrow和Friends以及Ivy和Friends，它们提供了在分布式环境中实现原子操作的方法。 **最大独立集（Maximal Independent Set，MIS）**是图论中的一个重要概念，第7章详细介绍了不同版本的快速MIS算法及其应用。 **局部性下界（Locality Lower Bounds）**探讨了在分布式系统中如何利用空间局部性。第8章明确了模型，并分析了局部性的意义以及邻域图的概念。 最后，第9章关注**社交网络（Social Networks）**，这在现代分布式计算中是一个日益重要的主题。 这本书提供了分布式计算的全面概述，包括理论基础和实用算法，对于学习和理解分布式系统的运作原理极具价值。