Cooperative Data Exchange

As the number of wireless devices grows larger worldwide every day, there are also more and more devices in our proximity. We assume that such “geographically close” wireless points form an autonomous local network over which the users can communicate and exchange files without contacting the base station. Such scenario may occur for instance when co-workers are using their tablets to share and update files stored in the cloud (e.g. Dropbox), or when users, in the subway or a mall, are interested in watching the same popular video. The main theme of this work is to utilize the benefits of communicating over a local network.

In this project we consider a file delivery system where a base station wants to transfer the same file to multiple geographically-close users over an unreliable wireless downlink. At the base station the file is split into packets which are then transmitted to the users over an unreliable wireless channel. As a result each user received some subset of the file packets. If the mobile users are in close vicinity and can communicate with each other, then it is much more desirable and efficient, in terms of resource usage, to reconcile the file among users by letting them “talk” to each other (over a public noiseless channel) without involving the base station. This cooperation has the following advantages: •The connection to the base station is either unavailable after the initial phase of transmission, or it is too weak to meet the delay requirements. •Local transmissions within the close group of users are much more reliable than from any user to the base station due to geographical proximity.

In this work we are interested in constructing a deterministic communication scheme that minimizes the (possibly weighted) amount of bits that users need to exchange over a local public channel in order for all of them to learn the entire file. This problem can be solved by answering the following two questions:

1.How many bits should each user transmit? 2.What should each user transmit?

We answer Question 1 by proposing a polynomial time (in number of users) algorithm that is based on some combinatorial optimization techniques. Moreover, this algorithm allows arbitrary correlations among the packets, and thus it can be applied to the various cases of the content distribution systems which use coding, such as Fountain codes or linear network codes. In such scenarios each user receives some linear combinations of the file packets. For this linear case, Question 2 can be addressed in polynomial time by considering the network coding solutions to the multicast problems.

Publications

1. N. Milosavljevic, S. Pawar, S. El Rouayheb, M. Gastpar and K. Ramchandran, “An Optimal Divide-and-Conquer Solution to the Linear Data Exchange Problem,” in Proceedings of ISIT 2011.

2. N. Milosavljevic, S. Pawar, S. El Rouayheb, M. Gastpar and K. Ramchandran, “Optimal Determinstic Polynomial-Time Data Exchange for Omniscience,” Arxiv