Improved algorithm in parallel computation model is faster than existing static parallel APSP algorithms

In recent years, the Massively Parallel Computation (MPC) model has gained significant attention. However, most 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 address this issue, a research team led by Qiang-Sheng Hua has published their research in Frontiers of Computer Science.

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, the team 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 demonstrated its effectiveness.