Design patterns in beeping algorithms: Examples, emulation, and analysis

We consider networks of entities which interact using beeps. In the basic model by Cornejo and Kuhn (2010), entities either beep or listen in each round. Those who beep cannot detect simultaneous beeps. Those who listen distinguish only between silence and non-silence. We call this model BL (beep or listen). Stronger models enable collision detection when beeping ( B c d L ), listening ( B L c d ), or both ( B c d L c d ). We identify a set of generic design patterns in beeping algorithms: multi-slot phases; exclusive beeps; adaptive probability; internal or peripheral collision detection (and their emulation). Using them, we formulate concisely a number of algorithms for basic tasks like colouring, degree computation, and MIS. We analyse their complexities, improving known bounds of the MIS algorithm by Jeavons et al. (2016). Finally, inspired by Afek et al. (2013), we show that all Las Vegas algorithms using collision detection are convertible into Monte Carlo algorithms with emulated detection, with a logarithmic slowdown.

Authors

• A. Casteigts
• Y. Métivier
• J.M. Robson
• A. Zemmari

Keywords

• Beeping models
• Design patterns
• Collision detection
• Colouring
• 2-hop colouring
• Degree computation
• Emulation