Deterministic multi-channel information exchange

作者：

Highlights：

• Deterministic algorithms for the Information Exchange Problem of k information items.

• Asymptotically optimal time complexity of Θ(k) with multiple communication channels.

• Upper and lower bounds on the number of channels needed for time Θ(k).

• Introduction of bipartite expander graphs with matching property useful for problem.

摘要

•Deterministic algorithms for the Information Exchange Problem of k information items.•Asymptotically optimal time complexity of Θ(k) with multiple communication channels.•Upper and lower bounds on the number of channels needed for time Θ(k).•Introduction of bipartite expander graphs with matching property useful for problem.

论文关键词：Information exchange problem,k-selection,Many-to-all communication,Multi-message broadcast,Multiple access channel,Multi-channel,Wireless computing,Single-hop networks,Deterministic algorithms and lower bounds

论文评审过程：Received 23 October 2014, Revised 10 February 2017, Accepted 18 February 2017, Available online 7 March 2017, Version of Record 11 April 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.02.006