A randomized algorithm and performance bounds for coded cooperative data exchange

Alex Sprintson, Parastoo Sadeghi, Graham Booker, Salim El Rouayheb

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

71 Scopus citations

Abstract

We consider scenarios where wireless clients are missing some packets, but they collectively know every packet. The clients collaborate to exchange missing packets over an error-free broadcast channel with capacity of one packet per channel use. First, we present an algorithm that allows each client to obtain missing packets, with minimum number of transmissions. The algorithm employs random linear coding over a sufficiently large field. Next, we show that the field size can be reduced while maintaining the same number of transmissions. Finally, we establish lower and upper bounds on the minimum number of transmissions that are easily computable and often tight as demonstrated by numerical simulations.

Original languageEnglish (US)
Title of host publication2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Pages1888-1892
Number of pages5
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 IEEE International Symposium on Information Theory, ISIT 2010 - Austin, TX, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8103

Other

Other2010 IEEE International Symposium on Information Theory, ISIT 2010
Country/TerritoryUnited States
CityAustin, TX
Period6/13/106/18/10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A randomized algorithm and performance bounds for coded cooperative data exchange'. Together they form a unique fingerprint.

Cite this