Coded Computing for Distributed Graph Analytics
Coded Computing for Distributed Graph Analytics
复制标题
DOI：
10.1109/tit.2020.2999675
复制
发表时间：
2018-01
期刊：
影响因子：
--
通讯作者：
Saurav Prakash;Amirhossein Reisizadeh;Ramtin Pedarsani;A. Avestimehr
中科院分区：
文献类型：
--
作者：
Saurav Prakash;Amirhossein Reisizadeh;Ramtin Pedarsani;A. Avestimehr
为了高效地处理海量图，最近开发了许多分布式图计算系统。这些系统在计算的每一步都需要在计算机器之间交换许多消息，这使得通信带宽成为主要的性能瓶颈。我们提出了一个编码计算框架，该框架系统地在计算阶段注入冗余，从而使通信阶段的编码机会得以实现，从而大大减少了通信负载。具体来说，我们提出了编码方案，使Erdös-Rényi （ER）随机图的计算负载和平均通信负载之间的逆线性权衡（渐近）。随着图的大小$n\rightarrow\infty$，所提出的ER图方案是渐近最优的。对于有限的$n$，我们通过数值分析证明，对于给定的计算负载$r$，即当每个图顶点都小心地存储在$r$服务器上时，所提出的方案将平均通信负载削减（近）$r$。
Many distributed graph computing systems have been developed recently for efficient processing of massive graphs. These systems require many messages to be exchanged among computing machines at each step of the computation, making communication bandwidth a major performance bottleneck. We present a coded computing framework that systematically injects redundancy in the computation phase to enable coding opportunities in the communication phase thus reducing the communication load substantially. Specifically, we propose coded schemes that enable an inverse-linear trade-off (asymptotically) between computation load and average communication load for Erdös-Rényi (ER) random graph. The proposed scheme for ER graph is shown to be optimal asymptotically as the graph size $n\rightarrow\infty$. For finite $n$, we demonstrate via numerical analysis that 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) $r$.