Deterministic algorithm for the cooperative data exchange problem

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

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

43 Scopus citations

Abstract

In this paper we study the problem of data exchange, where each node in the system has a number of linear combinations of the data packets. Communicating over a public channel, the goal is for all nodes to reconstruct the entire set of the data packets in minimal total number of bits exchanged over the channel. We present a novel divide and conquer based architecture that determines the number of bits each node should transmit. This along with the well known fact, that it is sufficient for the nodes to broadcast linear combinations of their local information, provides a polynomial time deterministic algorithm for reconstructing the entire set of the data packets at all nodes in minimal amount of total communication.

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages410-414
Number of pages5
DOIs
StatePublished - 2011
Externally publishedYes
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: Jul 31 2011Aug 5 2011

Publication series

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

Other

Other2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Country/TerritoryRussian Federation
CitySt. Petersburg
Period7/31/118/5/11

All Science Journal Classification (ASJC) codes

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

Fingerprint

Dive into the research topics of 'Deterministic algorithm for the cooperative data exchange problem'. Together they form a unique fingerprint.

Cite this