Massively Parallel Algorithms for Distance Approximation and Spanners
share
Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms—usually sublogarithimic-time and often poly(loglog n)-time, or even faster—for a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widely-adopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an all-to-all manner to process large-scale data. Contributing to this line of work on MPC graph algorithms, we present poly(log k) ∈poly(loglog n) round MPC algorithms for computing O(k^1+o(1))-spanners in the strongly sublinear regime of local memory. One important consequence, by letting k = log n, is a O(log^2log n)-round algorithm for O(log^1+o(1) n) approximation of all pairs shortest path (APSP) in the near-linear regime of local memory. To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for computing spanners and distance approximation.
READ FULL TEXT