论文标题
通过碰撞检测，确切的确定性无线电广播
Exactly Optimal Deterministic Radio Broadcasting with Collision Detection
论文作者
论文摘要
我们考虑使用碰撞检测的同步无线电广播模型中的广播问题。网络的一个节点被网络中的所有节点都必须学到一条消息。我们提供了一种在蜂示模型上使用的确定性算法，该算法是带有碰撞检测的无线电广播模型的受限版本。该算法在以前的算法的圆形复杂性上提高了。通过碰撞检测，我们证明了无线电广播模型中完全匹配的下限。这表明，通过碰撞检测提供的无线电广播模型提供的额外功率无助于提高圆形复杂性。
We consider the broadcast problem in synchronous radio broadcast models with collision detection. One node of the network is given a message that must be learned by all nodes in the network. We provide a deterministic algorithm that works on the beeping model, which is a restricted version of the radio broadcast model with collision detection. This algorithm improves on the round complexity of previous algorithms. We prove an exactly matching lower bound in the radio broadcast model with collision detection. This shows that the extra power provided by the radio broadcast model with collision detection does not help improve the round complexity.
