Optimal Deterministic Polynomial-Time Data Exchange for Omniscience

Details Optimal Deterministic Polynomial-Time Data Exchange for Omniscience Optimal Deterministic Polynomial-Time Data Exchange for Omniscience

2011-08-30

arxiv.org/abs/1108.6046v1

Computer Science

Information Theory

Scientific paper

We study the problem of constructing a deterministic polynomial time algorithm that achieves omniscience, in a rate-optimal manner, among a set of users that are interested in a common file but each has only partial knowledge about it as side-information. Assuming that the collective information among all the users is sufficient to allow the reconstruction of the entire file, the goal is to minimize the (possibly weighted) amount of bits that these users need to exchange over a noiseless public channel in order for all of them to learn the entire file. Using established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing a maximum size secret shared key in the presence of an eavesdropper. We consider the following types of side-information settings: (i) side information in the form of uncoded fragments/packets of the file, where the users' side-information consists of subsets of the file; (ii) side information in the form of linearly correlated packets, where the users have access to linear combinations of the file packets; and (iii) the general setting where the the users' side-information has an arbitrary (i.i.d.) correlation structure. Building on results from combinatorial optimization, we provide a polynomial-time algorithm (in the number of users) that, first finds the optimal rate allocations among these users, then determines an explicit transmission scheme (i.e., a description of which user should transmit what information) for cases (i) and (ii).

Affiliated with

Also associated with

No associations

Rating

Optimal Deterministic Polynomial-Time Data Exchange for Omniscience 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 Optimal Deterministic Polynomial-Time Data Exchange for Omniscience, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Deterministic Polynomial-Time Data Exchange for Omniscience will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-729138