On coding for cooperative data exchange

Salim El Rouayheb, Alex Sprintson, Parastoo Sadeghi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

99 Scopus citations

Abstract

We consider the problem of data exchange by a group of closely-located wireless nodes. In this problem each node holds a set of packets and needs to obtain all the packets held by other nodes. Each of the nodes can broadcast the packets in its possession (or a combination thereof) via a noiseless broadcast channel of capacity one packet per channel use. The goal is to minimize the total number of transmissions needed to satisfy the demands of all the nodes, assuming that they can cooperate with each other and are fully aware of the packet sets available to other nodes. This problem arises in several practical settings, such as peer-to-peer systems and wireless data broadcast. In this paper, we establish upper and lower bounds on the optimal number of transmissions and present an efficient algorithm with provable performance guarantees. The effectiveness of our algorithms is established through numerical simulations.

Original languageEnglish (US)
Title of host publicationIEEE Information Theory Workshop 2010, ITW 2010
DOIs
StatePublished - 2010
Externally publishedYes
EventIEEE Information Theory Workshop 2010, ITW 2010 - Cairo, Egypt
Duration: Jan 6 2010Jan 8 2010

Publication series

NameIEEE Information Theory Workshop 2010, ITW 2010

Other

OtherIEEE Information Theory Workshop 2010, ITW 2010
Country/TerritoryEgypt
CityCairo
Period1/6/101/8/10

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'On coding for cooperative data exchange'. Together they form a unique fingerprint.

Cite this