Optimal Multi-Broadcast with Beeps using Group Testing

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

1 LRI - Laboratoire de Recherche en Informatique
2 DIMAP - Centre for Discrete Mathematics and its Applications [Warwick]
3 ParSys - LRI - Systèmes parallèles (LRI)

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. The originality of our approach lies in the use of (combinatorial) group testing strategies, originally developed in the centralized context. We improve on previous solutions to multi-broadcast by giving efficiently constructible solutions, that is, with local computation cost polynomial in the identifiers' range.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Joffroy Beauquier, Janna Burman, Peter Davies, Fabien Dufoulon. Optimal Multi-Broadcast with Beeps using Group Testing. 2019. ⟨hal-02140017⟩