For over a decade now we have been witnessing the success of {\em massive
parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or
Spark. One of the reasons for their success is the fact that these frameworks
are able to accurately capture the nature of large-scale computation. In
particular, compared to the classic distributed algorithms or PRAM models,
these frameworks allow for much more local computation. The fundamental
question that arises in this context is though: can we leverage this additional
power to obtain even faster parallel algorithms?
A prominent example here is the {\em maximum matching} problem---one of the
most classic graph problems. It is well known that in the PRAM model one can
compute a 2-approximate maximum matching in $O(\log{n})$ rounds. However, the
exact complexity of this problem in the MPC framework is still far from
understood. Lattanzi et al. showed that if each machine has $n^{1+\Omega(1)}$
memory, this problem can also be solved $2$-approximately in a constant number
of rounds. These techniques, as well as the approaches developed in the follow
up work, seem though to get stuck in a fundamental way at roughly $O(\log{n})$
rounds once we enter the near-linear memory regime. It is thus entirely
possible that in this regime, which captures in particular the case of sparse
graph computations, the best MPC round complexity matches what one can already
get in the PRAM model, without the need to take advantage of the extra local
computation power.
In this paper, we finally refute that perplexing possibility. That is, we
break the above $O(\log n)$ round complexity bound even in the case of {\em
slightly sublinear} memory per machine. In fact, our improvement here is {\em
almost exponential}: we are able to deliver a $(2+\epsilon)$-approximation to
maximum matching, for any fixed constant $\epsilon>0$, in $O((\log \log n)^2)$
rounds.

该篇论文探讨了在大规模计算框架中对于最大匹配问题的解决方法，最终在机器拥有稍微低于线性内存的条件下，实现了近乎指数级的算法复杂度优化。

并行匹配算法的圆形压缩

Round Compression for Parallel Matching Algorithms

A common approach for designing scalable algorithms for massive data sets is
to distribute the computation across, say $k$, machines and process the data
using limited communication between them. A particularly appealing framework
here is the simultaneous communication model whereby each machine constructs a
small representative summary of its own data and one obtains an
approximate/exact solution from the union of the representative summaries. If
the representative summaries needed for a problem are small, then this results
in a communication-efficient and round-optimal protocol. While many fundamental
graph problems admit efficient solutions in this model, two prominent problems
are notably absent from the list of successes, namely, the maximum matching
problem and the minimum vertex cover problem. Indeed, it was shown recently
that for both these problems, even achieving a polylog$(n)$ approximation
requires essentially sending the entire input graph from each machine.
The main insight of our work is that the intractability of matching and
vertex cover in the simultaneous communication model is inherently connected to
an adversarial partitioning of the underlying graph across machines. We show
that when the underlying graph is randomly partitioned across machines, both
these problems admit randomized composable coresets of size $\widetilde{O}(n)$
that yield an $\widetilde{O}(1)$-approximate solution. This results in an
$\widetilde{O}(1)$-approximation simultaneous protocol for these problems with
$\widetilde{O}(nk)$ total communication when the input is randomly partitioned
across $k$ machines. We further prove the optimality of our results. Finally,
by a standard application of composable coresets, our results also imply
MapReduce algorithms with the same approximation guarantee in one or two rounds
of communication

本研究证明，匹配问题和点覆盖问题在同时通信模型中的不可承受性根源于基础图形跨机器的对抗性分区，进而展示这两个问题存在随机组分的可组合核的对数 O (n)。