The Effects of Locality on Efficient Distributed Computation

我们生活在一个互联互通日益增强的时代。在一台机器上进行计算的日子即将结束，现在我们的系统通常由一组独立的设备组成，这些设备必须在没有中央协调器的情况下进行交互才能实现目标。这种转变带来了许多新的挑战，迫使我们以不同的方式思考算法和计算。分布式算法设计独特的一个核心问题是“局部性”，这是一个术语，意味着每个设备关于整个系统的信息可能非常有限，或者只能查看附近的其他设备并与其通信。

We live in an era of increasing connectivity. The days where computation happens at a single machine are coming to an end, and now our systems often comprise of a set of independent devices that have to interact to accomplish a goal without a central coordinator. This shift has introduced many new challenges and has forced us to think about algorithms and computation in a different way. One central issue that is unique to distributed algorithm design is that of "locality", a term that means that each device might have very limited information about the entire system, or can only view and communicate with other nearby devices.