Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, L'Aquila, Italy, July 1-4, 2019, Proceedings
Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, L'Aquila, Italy, July 1-4, 2019, Proceedings
复制标题
结构信息与通信复杂性 - 第 26 届国际学术讨论会，SIROCCO 2019，意大利拉奎拉，2019 年 7 月 1-4 日，会议记录
DOI：
10.1007/978-3-030-24922-9_5
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Beauquier J
中科院分区：
文献类型：
--
作者：
Beauquier J
蜂鸣声模型是一种极具限制性的广播通信模型，仅依赖于载波感知。在该模型中，我们得到了多广播基本通信任务的时间最优解和确定性解。所提出的解是完全一致的，即不依赖于网络和问题参数。我们改进了先前的多广播结果，给出了有效的可构造解决方案，即在标识符范围内使用局部计算代价多项式。我们方法的独创性在于使用（组合）组测试策略，最初是在集中式环境中开发的。
Thebeeping modelis an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we obtaintime-optimal and deterministicsolutions for the fundamental communication task of multi-broadcast. The proposed solutions are completely uniform, i.e., independent of the network and problem parameters.We improve on previous results for multi-broadcast by givingefficiently constructiblesolutions, that is, with local computation cost polynomial in the identifiers’ range. The originality of our approach lies in the use of(combinatorial) group testing strategies, originally developed in the centralized context.