Theoretical Foundations of Modern Parallel and Distributed Algorithms

随着数据量的迅速增长以及分布式系统和网络的普及，人们普遍认为分布式和并行计算将在未来的计算中发挥非常重要的作用。这个项目将解决现代并行和分布式计算中的核心挑战之一，即推进基本图问题的并行和分布式算法的理论基础。这个项目的目标是通过提供新的方法来支持为该领域的基本问题设计高质量的算法，并通过提供新的技术来研究它们的局限性，从而推动我们在图和组合优化问题的并行和分布式算法领域的知识障碍。主要的技术目标是开发算法技术和数学工具，用于分析各种环境中的并行和分布式算法。我们主要关注这一领域的基础理论研究。这项建议的主要主题是在算法分析中利用PI的尖端专业知识-利用大规模并行和分布式计算模型理论框架之间的紧密联系-探索大规模并行计算(MPC)模型在随机化和确定性算法背景下的能力，以及-推进分布式算法领域(在本地、拥堵、拥挤的集团和特别网络模型中)。该项目将依赖PI在并行和分布式算法领域的国际公认的专业知识。它还将受益于华威大学在算法方面进行尖端研究的良好研究环境，以及PI与该领域世界领先科学家的广泛合作。

With the rapidly growing size of the data and the pervasiveness of distributed systems and networks, it is widely recognised that distributed and parallel computation will play a very prominent role in the computation of the future. This project will address one of the central challenges in modern parallel and distributed computation of advancing theoretical foundations of parallel and distributed algorithms for fundamental graphs problems. The objective of this project is to push forward the barriers of our knowledge in the area of parallel and distributed algorithms for graph and combinatorial optimisation problems by providing new methods to support the design of good quality algorithms for fundamental problems in this area and by providing new techniques to study their limitations. The main technical goal is to develop algorithmic technology and mathematical tools for the analysis of parallel and distributed algorithms in various settings. Our main focus is on fundamental theoretical research of this area. The main theme of this proposal is to utilise the cutting edge expertise of the PI in the analysis of algorithms- to exploit the close connection between the theoretical frameworks of massively parallel and distributed models of computation,- to explore the power of the Massively Parallel Computation (MPC) model in the context of randomised and deterministic algorithms, and- to advance the area of distributed algorithms (in the LOCAL, CONGEST, CONGESTED CLIQUE and ad-hoc network models) for fundamental graph problems.The project will rely on the internationally recognised expertise of the PI in the areas of parallel and distributed algorithms. It will also benefit from the excellent research environment at the University of Warwick to carry out cutting-edge research in algorithms and from the extensive collaboration of the PI with world leading scientists in the field.