Cooperative data exchange based on MDS codes

The coded cooperative data exchange problem is studied for the fully connected network. In this problem, each node initially only possesses a subset of the K packets making up the file. Nodes make broadcast transmissions that are received by all other nodes. The goal is for each node to recover the full file. In this paper, we present a polynomial-time deterministic algorithm to compute the optimal (i.e., minimal) number of required broadcast transmissions and to determine the precise transmissions to be made by the nodes. A particular feature of our approach is that each of the K − d transmissions is a linear combination of exactly d + 1 packets, and we show how to optimally choose the value of d. We also show how the coefficients of these linear combinations can be chosen by leveraging a connection to Maximum Distance Separable (MDS) codes.

Published in:
Proceedings of the 2017 IEEE International Symposium on Information Theory
Presented at:
2017 IEEE International Symposium on Information Theory, Aachen, Germany, June 25-30, 2017

 Record created 2017-08-18, last modified 2018-09-13

External link:
Download fulltext
Rate this document:

Rate this document:
(Not yet reviewed)