Computer Science – Information Theory
Scientific paper
2012-02-08
Computer Science
Information Theory
Scientific paper
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; (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).
Gastpar Michael
Milosavljevic Nebojsa
Pawar Sameer
Ramchandran Kannan
Rouayheb Salim El
No associations
LandOfFree
Data Exchange Problem with Helpers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Data Exchange Problem with Helpers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data Exchange Problem with Helpers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-64132