We consider networks of processes which interact with beeps. In the basicmodel defined by Cornejo and Kuhn (2010), processes can choose in each roundeither to beep or to listen. Those who beep are unable to detect simultaneousbeeps. Those who listen can only distinguish between silence and the presenceof at least one beep. We refer to this model as $BL$ (beep or listen). Strongermodels exist where the nodes can detect collision while they are beeping($B_{cd}L$), listening ($BL_{cd}$), or both ($B_{cd}L_{cd}$). Beeping modelsare weak in essence and even simple tasks are difficult or unfeasible within. We present a set of generic building blocks (design patterns) which seem tooccur frequently in the design of beeping algorithms. They include multi-slotphases: the fact of dividing the main loop into a number of specialised slots;exclusive beeps: having a single node beep at a time in a neighbourhood (withinone or two hops); adaptive probability: increasing or decreasing theprobability of beeping to produce more exclusive beeps; internal (resp.peripheral) collision detection: for detecting collision while beeping (resp.listening). Based on these patterns, we provide algorithms for a number ofbasic problems, including colouring, 2-hop colouring, degree computation, 2-hopMIS, and collision detection (in $BL$). The patterns make it possible toformulate these algorithms in a rather concise and elegant way. Their analysesare more technical; one of them improves significantly upon that of the bestknown MIS algorithm by Jeavons et al. (2016). Finally, inspired by a techniquefrom Afek et al. (2013), our last contribution is to show that any Las Vegasalgorithm relying on collision detection can be transposed into a Monte Carloalgorithm without collision detection at the cost of a logarithmic slowdown,which we prove is optimal.
展开▼
