2022/02/13 by Koko Nanah Ji, Ji, Koko Nanah
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2202.06375
openalex publication_date 2022/02/13 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
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.