Coded Computing for Distributed Graph Analytics

摘要: Many distributed graph computing systems have been developed recently for efficient processing of massive graphs. These require many messages to be exchanged among machines at each step the computation, making communication bandwidth a major performance bottleneck. We present coded framework that systematically injects redundancy in computation phase enable coding opportunities thus reducing load substantially. Specifically, we propose schemes an inverse-linear trade-off (asymptotically) between and average Erdos-Renyi (ER) random graph. The proposed scheme ER is shown optimal asymptotically as size $n\rightarrow\infty$ . For finite $n$ , demonstrate via numerical analysis given $r$ i.e. when vertex carefully stored servers, slashes by (nearly)