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.
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.
People |
ORCID iD |
| Artur Czumaj (Principal Investigator) |
Publications
Coy S
(2023)
Deterministic Massively Parallel Connectivity
in SIAM Journal on Computing
Bishnu A
(2023)
Almost optimal query algorithm for hitting set using a subset query
in Journal of Computer and System Sciences
Czumaj A
(2023)
On parallel time in population protocols
in Information Processing Letters
Coy S
(2023)
On Parallel k-Center Clustering
Chakraborty S
(2022)
Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing
Ghosh, Arijit ; Mishra, Gopinath ; Raychaudhury, Rahul ; Sen, Sayantan
(2022)
Tolerant Bipartiteness Testing in Dense Graphs
Coy S
(2022)
Deterministic massively parallel connectivity
Czumaj A
(2022)
Streaming Algorithms for Geometric Steiner Forest
Sam Coy
(2022)
Near-Shortest Path Routing in Hybrid Communication Networks
Czumaj A
(2022)
Haystack hunting hints and locker room communication
in Random Structures & Algorithms
Artur Czumaj
(2021)
Haystack hunting hints and locker room communication
Czumaj A
(2021)
Improved Deterministic (?+1) Coloring in Low-Space MPC
Artur Czumaj
(2021)
On Truly Parallel Time in Population Protocols
Czumaj A
(2021)
Component Stability in Low-Space Massively Parallel Computation
| Description | Co-organizing Simons Semester: Algorithms for Massive Parallel Computation Model (April - June 2022) |
| Organisation | Simons Foundation |
| Country | United States |
| Sector | Charity/Non Profit |
| PI Contribution | As one of (three) main organizers of this event, I will be bringing world-leading experts in the area of parallel and distribued computing, and will be involved in running two workshops during the semester. |
| Collaborator Contribution | Simons Semesters at Banach Center (Poland) are international scientific short term programmes funded by Simons Foundation, intended to support institutions in the mathematics and physical sciences through funding to centers of excellence, to help establish scientific culture and strengthen contacts within the international scientific community. We expect world-leading researcher participating in the activities (though, alas, because of the combination of the impact of Covid-19 pandemic and the war in Ukraine, it's likely the participation will be in th hybrid mode). |
| Impact | The contributions are mostly via enhanncing international collaboration in the area of the EPSRC grant, and possibly, will lead to more research publications and enhanced visibility of my research. |
| Start Year | 2022 |
| Description | Modern Parallel Algorithms: Graduate level minicourse, University of Warsaw, Warsaw, Poland, November 2022 |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | National |
| Primary Audience | Postgraduate students |
| Results and Impact | This was a graduate level minicourse entitled "Modern Parallel Algorithms", which took place in Institute of Informatics, at the Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw, Warsaw, Poland, November 2022. The course was taken by about a dozen of MSc and PhD students from Poland (mostly from the University of Warsaw). In this lecture series we discussed some of the recent advances in the design and analysis of "modern" parallel algorithms. For over a decade now we have been witnessing the success of massive parallel computation frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms? We addressed this question in the setting of the Massively Parallel Computation (MPC) model, which is an emerging model which distills core aspects of parallel and distributed computation. The MPC model has been developed as a tool to solve (typically graph) problems in systems where the input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear memory. This course introduced this model and presented some recent advances for fundamental problems in this area, with the focus on graph problems. |
| Year(s) Of Engagement Activity | 2022 |
| URL | https://phdopen.mimuw.edu.pl/index.php?page=z22w2 |
| Description | Simons Institute Semester on Sublinear Algorithms, to be held at Simons Institute for the Theory of Computing, University of California Berkeley, CA, USA, May 20 -- August 9, 2024 (organised by Clement Canonne (University of Sydney, Australia), Artur Czumaj (University of Warwick, UK), Piotr Indyk (MIT, USA), Jelani Nelson (UC Berkeley, USA), Noga Ron-Zewi (University of Haifa, Israel), Ronitt Rubinfeld (MIT, USA), Asaf Shapira (Tel Aviv University, Israel)) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | This is a major international research program (with me as one of the main organisers) to be run at the Simons Institute for the Theory of Computing (https://simons.berkeley.edu/), UC Berkeley, CA, USA, in 2024. The entire program should involve over a 100 academics, post-docs, graduate students, researchers in international laboratories (e.g., Google, Yahoo, Facebook, etc), etc. This is typically a high-profile activity in the community, considered to be one of the big international events, and the topic of this special program is very related to the EPSRC grant, and my contributions to the research in this area have been supported by EPSRC. |
| Year(s) Of Engagement Activity | 2023 |
| Description | Workshop on Emerging Models of Colossal Computiation (E=mc2), Warsaw, Poland, May 16 - 18, 2022 (co-organized by Artur Czumaj (University of Warwick, UK), Krzysztof Onak (Boston University), Piotr Sankowski (IDEAS NCBR & University of Warsaw), Martin Schulz (Technical University of Munich), and Jesper Larsson Träff (TU Wien)) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | This was an internation workshop bringing together two quite disjoint communities: - systems researchers working on parallel and distributed data processing systems and theoreticians interested in developing algorithms for such systems. The event provided a great oportunity to learn about current research trends in both communities, and in long term, we hope it will inspire both new connections and new practice-based models and approaches to analyzing practical big data computation in the context of parallel and distributed systems. |
| Year(s) Of Engagement Activity | 2022 |
| URL | https://ideas-ncbr.pl/en/emcc/ |