Efficient Algorithms for the Data Exchange Problem

Nebojsa Milosavljevic, Sameer Pawar, Salim El Rouayheb, Michael Gastpar, Kannan Ramchandran

Research output: Contribution to journalArticle

15 Citations (Scopus)

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.

Original languageEnglish (US)
Article number7398036
Pages (from-to)1878-1896
Number of pages19
JournalIEEE Transactions on Information Theory
Volume62
Issue number4
DOIs
StatePublished - Apr 1 2016
Externally publishedYes

Fingerprint

data exchange
Electronic data interchange
Communication
costs
communication
Cost functions
Costs
Linear networks
Network coding
Polynomials
broadcast
Recovery
coding

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Library and Information Sciences
  • Computer Science Applications

Keywords

  • Network coding
  • combinatorial mathematics
  • optimization
  • packet radio networks

Cite this

Milosavljevic, N., Pawar, S., El Rouayheb, S., Gastpar, M., & Ramchandran, K. (2016). Efficient Algorithms for the Data Exchange Problem. IEEE Transactions on Information Theory, 62(4), 1878-1896. [7398036]. https://doi.org/10.1109/TIT.2016.2523980
Milosavljevic, Nebojsa ; Pawar, Sameer ; El Rouayheb, Salim ; Gastpar, Michael ; Ramchandran, Kannan. / Efficient Algorithms for the Data Exchange Problem. In: IEEE Transactions on Information Theory. 2016 ; Vol. 62, No. 4. pp. 1878-1896.
@article{e49cd504ce4c43158eade264e05e2962,
title = "Efficient Algorithms for the Data Exchange Problem",
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 = "Network coding, combinatorial mathematics, optimization, packet radio networks",
author = "Nebojsa Milosavljevic and Sameer Pawar and {El Rouayheb}, Salim and Michael Gastpar and Kannan Ramchandran",
year = "2016",
month = "4",
day = "1",
doi = "https://doi.org/10.1109/TIT.2016.2523980",
language = "English (US)",
volume = "62",
pages = "1878--1896",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

Milosavljevic, N, Pawar, S, El Rouayheb, S, Gastpar, M & Ramchandran, K 2016, 'Efficient Algorithms for the Data Exchange Problem', IEEE Transactions on Information Theory, vol. 62, no. 4, 7398036, pp. 1878-1896. https://doi.org/10.1109/TIT.2016.2523980

Efficient Algorithms for the Data Exchange Problem. / Milosavljevic, Nebojsa; Pawar, Sameer; El Rouayheb, Salim; Gastpar, Michael; Ramchandran, Kannan.

In: IEEE Transactions on Information Theory, Vol. 62, No. 4, 7398036, 01.04.2016, p. 1878-1896.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Efficient Algorithms for the Data Exchange Problem

AU - Milosavljevic, Nebojsa

AU - Pawar, Sameer

AU - El Rouayheb, Salim

AU - Gastpar, Michael

AU - Ramchandran, Kannan

PY - 2016/4/1

Y1 - 2016/4/1

N2 - 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.

AB - 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.

KW - Network coding

KW - combinatorial mathematics

KW - optimization

KW - packet radio networks

UR - http://www.scopus.com/inward/record.url?scp=84963720618&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963720618&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/TIT.2016.2523980

DO - https://doi.org/10.1109/TIT.2016.2523980

M3 - Article

VL - 62

SP - 1878

EP - 1896

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 4

M1 - 7398036

ER -