License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.15
URN: urn:nbn:de:0030-drops-70840
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7084/
Casteigts, Arnaud ;
Métivier, Yves ;
Robson, John Michael ;
Zemmari, Akka
Design Patterns in Beeping Algorithms
Abstract
We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn, which we refer to as the BL variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Stronger variants exist where the nodes can also detect collision while they are beeping (B_{cd}L) or listening (BL_{cd}), or both (B_{cd}L_{cd}). Beeping models are weak in essence and even simple tasks are difficult or unfeasible with them.
This paper starts with a discussion on generic building blocks (design patterns) which seem to occur frequently in the design of beeping algorithms. They include multi-slot phases: 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 (within one or two hops); adaptive probability: increasing or decreasing the probability of beeping to produce more exclusive beeps; internal (resp. peripheral) collision detection: for detecting collision while beeping (resp. listening); and emulation of collision detection: for enabling this feature when it is not available as a primitive.
We then provide algorithms for a number of basic problems, including colouring, 2-hop colouring, degree computation, 2-hop MIS, and collision detection (in BL). Using the patterns, we formulate these algorithms in a rather concise and elegant way. Their analyses (in the full version) are more technical, e.g. one of them relies on a Martingale technique with non-independent variables; another improves that of the MIS algorithm (P. Jeavons et al.) by getting rid of a gigantic constant (the asymptotic order was already optimal).
Finally, we study the relative power of several variants of beeping models. In particular, we explain how every Las Vegas algorithm with collision detection can be converted, through emulation, into a Monte Carlo algorithm without, at the cost of a logarithmic slowdown. We prove that this slowdown is optimal up to a constant factor by giving a matching lower bound.
BibTeX - Entry
@InProceedings{casteigts_et_al:LIPIcs:2017:7084,
author = {Arnaud Casteigts and Yves M{\'e}tivier and John Michael Robson and Akka Zemmari},
title = {{Design Patterns in Beeping Algorithms}},
booktitle = {20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
pages = {15:1--15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-031-6},
ISSN = {1868-8969},
year = {2017},
volume = {70},
editor = {Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7084},
URN = {urn:nbn:de:0030-drops-70840},
doi = {10.4230/LIPIcs.OPODIS.2016.15},
annote = {Keywords: Beeping models, Design patterns, Collision detection, Colouring, 2-hop colouring, Degree computation, Emulation}
}
|
Keywords: |
|
Beeping models, Design patterns, Collision detection, Colouring, 2-hop colouring, Degree computation, Emulation |
|
Collection: |
|
20th International Conference on Principles of Distributed Systems (OPODIS 2016) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
06.04.2017 |
