Achieving Absolutely Optimal Block Pipelining in Organized Network Coded Gossip
Majid Khabbazian, Di Niu · 2014
We use random linear network coding 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 existing gossip schemes which rely on completely random contact, we prove that with random linear network coding, any receiver selection following a simple permutation rule can achieve a broadcast finish time of k + n and that a time-varying random permutation topology achieves a finish time of k + o (k) + O (log n), both with high probability. Since the theoretical limit on finish time is k + log2 n, our simple permutation algorithms achieve absolutely optimal (not only order-optimal) block pipelining for 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.