Theoretical Foundations of Modern Parallel and Distributed Algorithms

Lead Research Organisation: University of Warwick
Department Name: Computer Science

Abstract

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.

Publications

10 25 50