Optimal Multi-broadcast with Beeps Using Group Testing

Joffroy Beauquier (1) , Janna Burman (1) , Peter Davies (2) , Fabien Dufoulon (3, 4)

1 ParSys - Systèmes Parallèles - LISN
2 department of Computer science, Durham University
3 ParSys - LRI - Systèmes parallèles (LRI)
4 Computing Department [Lancaster]

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we obtain time-optimal and deterministic solutions 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 giving efficiently constructible solutions, 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.

Domaines: Informatique [cs]

Joffroy Beauquier, Janna Burman, Peter Davies, Fabien Dufoulon. Optimal Multi-broadcast with Beeps Using Group Testing. Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, Jul 2019, L'Aquila, Italy. pp.66-80, ⟨10.1007/978-3-030-24922-9_5⟩. ⟨hal-04475010⟩