Massively parallel algorithms for fully dynamic all-pairs shortest paths

In recent years, the Massively Parallel Computation (MPC) model has gained significant attention. However, most of distributed and parallel graph algorithms in the MPC model are designed for static graphs. Dynamic graph algorithms can deal with graph changes more efficiently than the corresponding static graph algorithms. Moreover, a few parallel dynamic graph algorithms (such as the graph connectivity) in the MPC model have been proposed and shown superiority over their parallel static counterparts. However, there are no existing dynamic all-pairs shortest paths (APSP) algorithms working in the MPC model.
To solve the problems, a research team led by Qiang-Sheng HUA published their new research on 15 August 2024 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The team designed a fully dynamic APSP algorithm in the MPC model with low round complexity that is faster than all the existing static parallel APSP algorithms. The proposed parallel fully dynamic APSP algorithm is based on a sequential dynamic APSP algorithm, whose direct implementation in the MPC model can result in a large round complexity which is inefficient. Moreover, the total memory required to store these data structures of this sequential dynamic APSP algorithm is too large.
To reduce the round complexity and to make the total memory required as small as possible, they improved the original sequential dynamic APSP algorithm by combining the graph algorithms (such as the restricted Bellman-Ford algorithm) and the algebraic methods (such as matrix multiplication on semiring) to reduce the round complexity and the total memory required. Furthermore, they provided a comparison of their algorithm with the existing static APSP algorithms in the MPC model and demonstrate its effectiveness.
DOI: 10.1007/s11704-024-3452-2