TY - GEN

T1 - Data exchange problem with helpers

AU - Milosavljevic, Nebojsa

AU - Pawar, Sameer

AU - Rouayheb, Salim El

AU - Gastpar, Michael

AU - Ramchandran, Kannan

PY - 2012

Y1 - 2012

N2 - In this paper we construct a deterministic polynomial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another set of terminals in the system, called helpers, who are not interested in the common file, but who are willing to help the users. Given that the collective information of all the terminals is sufficient to allow recovery of the entire file, the goal is to minimize the (weighted) sum of bits that these terminals need to exchange over a noiseless public channel in order achieve this goal. Based on established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing the largest shared secret key in the presence of an eavesdropper. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the terminals' side-information consists of subsets of the file packets; (ii) side-information in the form of linearly correlated packets, where the terminals have access to linear combinations of the file packets; and (iii) the general setting where the the terminals' side-information has an arbitrary (i.i.d.) correlation structure. We provide a polynomial-time algorithm (in the number of terminals) that finds the optimal rate allocations for these terminals, and then determines an explicit optimal transmission scheme for cases (i) and (ii).

AB - In this paper we construct a deterministic polynomial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another set of terminals in the system, called helpers, who are not interested in the common file, but who are willing to help the users. Given that the collective information of all the terminals is sufficient to allow recovery of the entire file, the goal is to minimize the (weighted) sum of bits that these terminals need to exchange over a noiseless public channel in order achieve this goal. Based on established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing the largest shared secret key in the presence of an eavesdropper. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the terminals' side-information consists of subsets of the file packets; (ii) side-information in the form of linearly correlated packets, where the terminals have access to linear combinations of the file packets; and (iii) the general setting where the the terminals' side-information has an arbitrary (i.i.d.) correlation structure. We provide a polynomial-time algorithm (in the number of terminals) that finds the optimal rate allocations for these terminals, and then determines an explicit optimal transmission scheme for cases (i) and (ii).

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

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

U2 - 10.1109/ISIT.2012.6283991

DO - 10.1109/ISIT.2012.6283991

M3 - Conference contribution

AN - SCOPUS:84867556651

SN - 9781467325790

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2611

EP - 2615

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

T2 - 2012 IEEE International Symposium on Information Theory, ISIT 2012

Y2 - 1 July 2012 through 6 July 2012

ER -