Improving Computational Efficiency of Communication for Omniscience and Successive Omniscience

Communication for omniscience (CO) refers to the problem where the users in a finite set $V$ observe a discrete multiple random source and want to exchange data over broadcast channels to reach omniscience, the state where everyone recovers the entire source. This paper studies how to improve the computational complexity for the problem of minimizing the sum-rate for attaining omniscience in $V$ . While the existing algorithms rely on the submodular function minimization (SFM) techniques and complete in $O(|V|^{2} \cdot \text {SFM} (|V|)$ time, we prove the strict strong map property of the nesting SFM problem. We propose a parametric (PAR) algorithm that utilizes the parametric SFM techniques and reduces the complexity to $O(|V| \cdot \text {SFM} (|V|)$ . We propose efficient solutions to the successive omniscience (SO): attaining omniscience successively in user subsets. We first focus on how to determine a complimentary subset $X_{*}\subsetneq V$ in the existing two-stage SO such that if the local omniscience in $X_{*}$ is reached first, the global omniscience whereafter can still be attained with the minimum sum-rate. It is shown that such a subset can be extracted at one of the iterations of the PAR algorithm. We then propose a novel multi-stage SO strategy: a nesting sequence of complimentary user subsets $X_{*}^{(1)} \subsetneq \dotsc \subsetneq X_{*}^{(K)} = V$ , the omniscience in which is attained progressively by the monotonic rate vectors $\mathbf {r}_{V}^{(1)} \leq \dotsc \leq \mathbf {r} _{V}^{(K)}$ . We propose algorithms to obtain this $K$ -stage SO from the returned results by the PAR algorithm. The run time of these algorithms is the same as the PAR algorithm.