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