Deterministic multi-channel information exchange

We study the information exchange problem on a set of multiple access channels: k arbitrary nodes have information they want to distribute to the entire network of n nodes via a shared medium partitioned into channels. We devise a deterministic algorithm running in asymptotically optimal time O(k) using O(nlog⁡(k)/k) channels if k≤16log⁡n and O(log1+ρ⁡(n/k)) channels otherwise, where ρ>0 is an arbitrarily small constant. This is a super-polynomial improvement over the best known bounds [20]. Additionally we show that our results are significantly closer to the optimal solution by proving that Ω(nΩ(1/k)+logk⁡n) channels are necessary to achieve a time complexity of O(k).