Achieving Optimal Block Pipelining in Organized Network Coded Gossip

作者：Khabbazian Majid^*; Niu Di^*

来源：IEEE Transactions on Parallel and Distributed Systems, 2016, 27(3): 627-639.

DOI：10.1109/TPDS.2015.2417163

• Network coding
• gossip
• broadcast finish time
• optimal block pipelining
• computer cluster
• content distribution
• randomized algorithms

We use randomized network coding (RNC) with simple connection topology control to approach the theoretical limit on finish time of disseminating k blocks in a server cluster of n nodes. Unlike prior gossip literature which relies on completely random contact, we prove that with RNC, any receiver selection following a simple permutation rule can achieve a broadcast completion time of k + n and that a time-varying random ring topology achieves a completion time of k + o(k) + O(log n), both with high probability. Since the theoretical limit on finish time is k + [log(2) n], our simple permutation algorithms achieve absolutely optimal (not only order-optimal) block pipelining for the k blocks. Our results hold for both one-to-all (broadcast) and all-to-all transfers. We demonstrate the usefulness of the proposed organized network coded gossip with an application to content distribution in cluster computing systems like MapReduce, and discuss practical block dividing strategies to hide the negative effect of computation overhead of network coding.

• 出版日期2016-3