Title: A Practical Approach for Successive Omniscience,
Abstract: The system that we study in this paper contains a set of users that observe a
discrete memoryless multiple source and communicate via noise-free channels
with the aim of attaining omniscience, the state that all users recover the
entire multiple source. We adopt the concept of successive omniscience (SO),
i.e., letting the local omniscience in some user subset be attained before the
global omniscience in the entire system, and consider the problem of how to
efficiently attain omniscience in a successive manner. Based on the existing
results on SO, we propose a CompSetSO algorithm for determining a complimentary
set, a user subset in which the local omniscience can be attained first without
increasing the sum-rate, the total number of communications, for the global
omniscience. We also derive a sufficient condition for a user subset to be
complimentary so that running the CompSetSO algorithm only requires a lower
bound, instead of the exact value, of the minimum sum-rate for attaining global
omniscience. The CompSetSO algorithm returns a complimentary user subset in
polynomial time. We show by example how to recursively apply the CompSetSO
algorithm so that the global omniscience can be attained by multi-stages of SO.