Mathematical Methods in Distributed Computing

这个跨学科项目的目标是在分布式系统分析中开发新的数学工具，并提高我们对分布式计算中的复杂性和可计算性界限的理解。几乎所有的计算系统，从火灾警报到互联网规模的服务，现在都是分布式的：它们由许多执行独立计算并相互通信以同步其活动的计算单元组成。我们对分布式计算的性能和可靠性的依赖变得越来越迫切。这里的主要复杂因素是现有的分布式应用程序、分布式计算模型和性能度量的巨大多样性，以及缺乏处理这种复杂性的数学工具。最近，为解决这一挑战进行了一项令人印象深刻的尝试：使用现代数学的一些最先进的分支，包括组合和代数拓扑学的元素，解决了分布式可计算性中一些长期存在的开放问题。这些措施包括证明不可能解决SET协议的基本问题，以及以无需等待的方式重新命名。然而，现有的拓扑学在分布式计算中的应用大多涉及理论上的肯定或否定结果，即证明在给定模型中给定问题不存在解或以非构造性的方式证明存在事实。除了少数例外，没有令人信服的例子使用先进的数学工具来设计新的高效算法。在更高的层面上，这项建议旨在更好地了解在特定的分布式环境中可以实现什么，不可以实现什么。特别是，我们打算应用现代数学的力量来推导新的算法和分布式计算问题的严格下限。

The goal of this interdisciplinary project is to develop new mathematical tools in the analysis of distributed systems and to improve our understanding of complexity and computability bounds in distributed computing. Practically all computing systems, from fire alarms to Internet-scale services, are nowadays distributed: they consist of a number of computing units performing independent computations and communicating with each other to synchronize their activities. Our dependence on performance and reliability of the distributed computing becomes more and more imminent.The main complication here is the existing immense diversity of distributed applications, models of distributed computations, and performance metrics, combined with the lack of mathematical tools to handle this complexity. Recently, an impressive attempt to address this challenge was made: a number of long-standing open questions in distributed computability were resolved using some of the most advanced branches of modern mathematics, including the elements of combinatorial and algebraic topology. These encompass proving impossibility of solving the fundamental problems of Set Agreement, and Renaming in the wait-free manner. However, most of the existing applications of topology in distributed computing concern theoretical positive or negative results, i.e., proving that no solution to a given problem in a given model exists or proving the existence fact in a non-constructive way. With a few exceptions, there are no convincing examples of using advanced mathematical tools to design new efficient algorithms. At a higher level, this proposal aims at better understanding of what can and what cannot be implemented in specific distributed environments. In particular, we intend to apply the power of modern mathematics in deriving new algorithms and tight lower bounds for distributed computing problems.