Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951224 | Journal of Computer and System Sciences | 2017 | 20 Pages |
Abstract
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).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Stephan Holzer, Thomas Locher, Yvonne Anne Pignolet, Roger Wattenhofer,