Efficient Algorithms for the Data Exchange Problem
Authors:
Open Access
- 3 February 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 62 (4) , 1878-1896
Abstract
In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file, while minimizing some communication cost. We assume that the users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user's cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this paper, each user can have any arbitrary convex cost function. We provide deterministic, polynomial-time algorithms (in the number of users and packets), which find an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm, which is based on a random linear network-coding scheme.Keywords
All Related Versions
Funding Information
- Defense Threat Reduction Agency (HDTRA1-09-1-0032)
- National Science Foundation (CCF-0964018, CCF-0830788)
- Air Force Office of Scientific Research (FA9550-09-1-0120, FA9550-10-1-0567)
This publication has 27 references indexed in Scilit:
- Coded Cooperative Data Exchange in Multihop NetworksIEEE Transactions on Information Theory, 2013
- Linear perfect secret key agreement2011
- Delay of linear perfect secret key agreement2011
- A Generalized Model for Cost and Fairness Analysis in Coded Cooperative Data Exchange2011
- A faster strongly polynomial time algorithm for submodular function minimizationMathematical Programming, 2007
- 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
- Convex Optimization2004
- Network information flowIEEE Transactions on Information Theory, 2000