Corelab Seminar

Chridtina Karousatou (NTUA)
All-Pairs Shortest Paths Computation in the BSP Model (Alexandre Tiskin)

Abstract (of the paper).
The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We propose a new p-processor BSP algorithm for the all-pairs shortest paths problem in a weighted directed dense graph. In contrast with the general algebraic path algorithm, which performs O(p^1/2) to O(p^2/3) global synchronisation steps, our new algorithm only requires O(logp) synchronisation steps.