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(n(log(k)/k)) channels if k <= 1/6 logn and O(log(1+rho)(n/k)) channels otherwise, where rho > 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 Omega(n(Omega(1/k)) + log(k)n) channels are necessary to achieve a time complexity of O(k). (C) 2017 Elsevier Inc. All rights reserved.