TY - GEN

T1 - Deterministic algorithm for the cooperative data exchange problem

AU - Milosavljevic, Nebojsa

AU - Pawar, Sameer

AU - El Rouayheb, Salim

AU - Gastpar, Michael

AU - Ramchandran, Kannan

PY - 2011

Y1 - 2011

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

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

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

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

U2 - 10.1109/ISIT.2011.6034157

DO - 10.1109/ISIT.2011.6034157

M3 - Conference contribution

AN - SCOPUS:80054809782

SN - 9781457705953

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 410

EP - 414

BT - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

T2 - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

Y2 - 31 July 2011 through 5 August 2011

ER -