Cooperative data exchange based on MDS codes
Open Access
- 1 June 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1411-1415
Abstract
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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Cooperative data exchange with priority classes2016
- Efficient Algorithms for the Data Exchange ProblemIEEE Transactions on Information Theory, 2016
- Cooperative data exchange with unreliable clients2015
- Coded Cooperative Data Exchange in Multihop NetworksIEEE Transactions on Information Theory, 2013
- Balanced Sparsest generator matrices for MDS codes2013
- Algorithms for weakly secure data exchange2013
- A Generalized Model for Cost and Fairness Analysis in Coded Cooperative Data Exchange2011
- A Random Linear Network Coding Approach to MulticastIEEE Transactions on Information Theory, 2006
- Polynomial Time Algorithms for Multicast Network Code ConstructionIEEE Transactions on Information Theory, 2005
- Secrecy Capacities for Multiple TerminalsIEEE Transactions on Information Theory, 2004