Performance of distributed graph processing systems significantly suffers
from 'communication bottleneck' as a large number of messages are exchanged
among servers at each step of the computation. Motivated by graph based
MapReduce, we propose a coded computing framework that leverages computation
redundancy to alleviate the communication bottleneck in distributed graph
processing. We develop a novel 'coding' scheme that systematically injects
structured redundancy in computation phase to enable 'coded' multicasting
opportunities during message exchange between servers, reducing communication
load substantially in large-scale graph processing. For theoretical analysis,
we consider random graph models, and prove that our proposed scheme enables an
(asymptotically) inverse-linear trade-off between 'computation load' and
'average communication load' for two popular random graph models -- Erdos-Renyi
model, and power law model. Particularly, for a given computation load r, (i.e.
when each graph vertex is carefully stored at r servers), the proposed scheme
slashes the average communication load by (nearly) a multiplicative factor of
r. For the Erdos-Renyi model, our proposed scheme is optimal asymptotically as
the graph size increases by providing an information-theoretic converse. To
illustrate the benefits of our scheme in practice, we implement PageRank over
Amazon EC2, using artificial as well as real-world datasets, demonstrating
significant gains over conventional PageRank. We also specialize our scheme and
extend our theoretical results to two other random graph models -- random
bi-partite model, and stochastic block model. They asymptotically enable
inverse-linear trade-offs between computation and communication loads in
distributed graph processing for these popular random graph models as well. We
complement the achievability results with converse bounds for both of these
models.

本文提出了一种基于编码计算的分布式图处理框架，通过结构性冗余注入来在消息交换时实现编码的多播机会，从而大规模减少了通信负载，理论分析证明该方案在两种流行的随机图模型（Erdos-Renyi 模型和幂律模型）中实现了计算负载和平均通信负载之间的（近似）反比例线性折衷，实验结果表明该方案在 PageRank 计算中具有显着提高。