Theoretical Foundations of Modern Parallel and Distributed Algorithms

随着数据量的快速增长和分布式系统和网络的普及，分布式和并行计算将在未来的计算中发挥非常重要的作用，这一点已经得到了广泛的认识。该项目将解决现代并行和分布式计算的核心挑战之一，即推进基本图问题并行和分布式算法的理论基础。该项目的目标是通过提供新方法来支持该领域基本问题的高质量算法的设计，并提供新技术来研究其局限性，从而推动我们在图和组合优化问题的并行和分布式算法领域的知识障碍。主要技术目标是开发算法技术和数学工具，用于分析各种设置下的并行和分布式算法。我们的主要重点是这一领域的基础理论研究。本提案的主题是利用PI在算法分析中的尖端专业知识-利用大规模并行和分布式计算模型的理论框架之间的密切联系，-在随机和确定性算法的背景下探索大规模并行计算（MPC）模型的功能，并且-推进分布式算法领域(在LOCAL， CONGEST，基本图问题的拥塞团和自组织网络模型。该项目将依靠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.