Author name cluster

A. Casteigts

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2019 Journal Article

Counting in one-hop beeping networks

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

We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn [8], 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. Beeping models are weak in essence and even simple tasks may become difficult or unfeasible with them. In this paper, we address the problem of computing how many participants there are in a one-hop network: the counting problem. We first observe that no algorithm can compute this number with certainty in BL, even if it is randomised (Las Vegas). We thus consider the stronger variant where beeping nodes are able to detect simultaneous beeps, referred to as B c d L (cd stands for collision detection). We prove that at least n rounds are necessary in B c d L, and we present an algorithm whose running time is O ( n ) rounds with high probability. Further experimental results show that its expected running time is less than 10n. Finally, we discuss how this algorithm can be adapted in other beeping models. In particular, we show that the algorithm can be emulated in BL, at the cost of a logarithmic slowdown and of trading its Las Vegas nature (certain result, uncertain time) against a Monte Carlo one (certain time, uncertain result).

Details DOI

I&C Journal 2019 Journal Article

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

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

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.

Details DOI