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 \text{poly (\log\log 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 \text{poly (\log k) \in \text{poly (\log\log 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^2\log 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 .
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 sublogarithmic-time and often poly (\log\log 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) \in poly (\log\log n) round MPC algorithms for computing O(k^{1+{o(1)}})-spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for spanner construction. As primary applications of our spanners, we get two important implications, as follows: -For the MPC setting, we get an O(\log^2\log n)-round algorithm for O(\log^{1+o(1)} n) approximation of all pairs shortest paths (APSP) in the near-linear regime of local memory. To the best of our knowledge, this is the first sublogarithmic-time MPC algorithm for distance approximations. -Our result above also extends to the Congested Clique model of distributed computing, with the same round complexity and approximation guarantee. This gives the first sub-logarithmic algorithm for approximating APSP in weighted graphs in the Congested Clique model .
R
sublogarithimic-time and often \text{poly
sublogarithmic-time and often poly
R
\text{poly
poly
R
\text{poly
poly
R
One important consequence, by letting k = \log n, is a
To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for spanner construction. As primary applications of our spanners, we get two important implications, as follows: -For the MPC setting, we get an
R
path
paths
R
these are
this is
R
algorithms for computing spanners and distance approximation
algorithm for distance approximations. -Our result above also extends to the Congested Clique model of distributed computing, with the same round complexity and approximation guarantee. This gives the first sub-logarithmic algorithm for approximating APSP in weighted graphs in the Congested Clique model