Arrow Research search

Author name cluster

Y. Métivier

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.

8 papers
1 author row

Possible papers

8

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

I&C Journal 2016 Journal Article

A distributed enumeration algorithm and applications to all pairs shortest paths, diameter…

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

We consider the standard message passing model; we assume the system is fully synchronous: all processes start at the same time and time proceeds in synchronised rounds. In each round each vertex can transmit a different message of size O ( 1 ) to each of its neighbours. This paper proposes and analyses a distributed enumeration algorithm of vertices of a graph having a distinguished vertex which satisfies that two vertices with consecutive numbers are at distance at most 3. We prove that its time complexity is O ( n ) where n is the number of vertices of the graph. Furthermore, the size of each message is O ( 1 ) thus its bit complexity is also O ( n ). We provide some links between this enumeration and Hamiltonian graphs from which we deduce that this enumeration is optimal in the sense that there does not exist an enumeration which satisfies that two vertices with consecutive numbers are at distance at most 2. We deduce from this enumeration, algorithms which compute all pairs shortest paths and the diameter with a time complexity and a bit complexity equal to O ( n ).

Details DOI

TCS Journal 2015 Journal Article

Analysis of fully distributed splitting and naming probabilistic procedures and applications

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

This paper proposes and analyses two fully distributed probabilistic splitting and naming procedures which assign a label to each vertex of a given anonymous graph G without any initial knowledge. We prove, in particular, that with probability 1 − o ( n − 1 ) (resp. with probability 1 − o ( n − c ) for any c ≥ 1 ) there is a unique vertex with the maximal label in the graph G having n vertices. In the first case, the size of labels is O ( log ⁡ n ) with probability 1 − o ( n − 1 ) and the expected value of the size of labels is also O ( log ⁡ n ). In the second case, the size of labels is O ( ( log ⁡ n ) ( log ⁎ ⁡ n ) 2 ) with probability 1 − o ( n − c ) for any c ≥ 1; their expected size is O ( ( log ⁡ n ) ( log ⁎ ⁡ n ) ). We analyse a basic simple maximum broadcasting algorithm and prove that if vertices of a graph G use the same probabilistic distribution to choose a label then, for broadcasting the maximal label over the labelled graph, each vertex sends O ( log ⁡ n ) messages with probability 1 − o ( n − 1 ). From these probabilistic procedures we deduce Monte Carlo algorithms for electing or computing a spanning tree in anonymous graphs without any initial knowledge and for counting vertices of an anonymous ring; these algorithms are correct with probability 1 − o ( n − 1 ) or with probability 1 − o ( n − c ) for any c ≥ 1. The size of messages has the same value as the size of labels. The number of messages is O ( m log ⁡ n ) for electing and computing a spanning tree; it is O ( n log ⁡ n ) for counting the vertices of a ring. These algorithms can be easily extended to also ensure for each vertex v an error probability bounded by ϵ v; the error probability ϵ v is decided by v in a totally decentralised way. We illustrate the power of the splitting procedure by giving a probabilistic election algorithm for rings having n vertices with identities which is correct and always terminates; its message complexity is equal to O ( n log ⁡ n ) with probability 1 − o ( n − 1 ).

Details DOI

TCS Journal 2013 Journal Article

On the time and the bit complexity of distributed randomised anonymous ring colouring

  • Y. Métivier
  • J.M. Robson
  • N. Saheb-Djahromi
  • A. Zemmari

We present and analyse a very simple randomised distributed vertex colouring algorithm for ring graphs. Its time complexity is log 2 n + o ( log n ) on average and 2 log 2 n + o ( log n ) with probability 1 − o ( n − 1 ). Since each message contains one bit, we deduce the same values for its bit complexity. Then we combine this algorithm with another and we obtain a 3-colouring algorithm for ring graphs. Thanks to an overlapping, we obtain once more the same values for the time complexities on average and with probability 1 − o ( n − 1 ). The same results hold for the bit complexity. These results are obtained using the Mellin transform. We establish lower bounds (on average and with probability 1 − o ( n − 1 ) ) for the distributed randomised anonymous ring colouring problem. We prove that our algorithms match these lower bounds modulo a negligible additive function (negligible with respect to log 2 n ). We assume that the ring is anonymous: unique identities are not available to distinguish the processes; we only assume that each vertex distinguishes between its neighbours. Furthermore, we do not assume that the size (or an upper bound on the size) of the ring is known.

Details DOI

I&C Journal 2013 Journal Article

Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings

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

We present and analyse Las Vegas distributed algorithms which compute a MIS or a maximal matching for anonymous rings. Their bit complexity and time complexity are O ( log n ) with high probability. These algorithms are optimal modulo a multiplicative constant. Beyond the complexity results, the interest of this work stands in the description and the analysis of these algorithms which may be easily generalised. Furthermore, these results show a separation between the complexity of the MIS problem (and of the maximal matching problem) on the one hand and the colouring problem on the other. Colouring can be computed only in Ω ( log n ) rounds on rings with high probability, while MIS is shown to have a faster algorithm. This is in contrast to other models, in which MIS is at least as hard as colouring.

Details DOI

I&C Journal 2010 Journal Article

About randomised distributed graph colouring and graph partition algorithms

  • Y. Métivier
  • J.M. Robson
  • N. Saheb-Djahromi
  • A. Zemmari

We present and analyse a very simple randomised distributed vertex colouring algorithm for arbitrary graphs of size n that halts in time O ( log n ) with probability 1 - o ( n - 1 ). Each message containing 1 bit, its bit complexity per channel is O ( log n ). From this algorithm, we deduce and analyse a randomised distributed vertex colouring algorithm for arbitrary graphs of maximum degree Δ and size n that uses at most Δ + 1 colours and halts in time O ( log n ) with probability 1 - o ( n - 1 ). We also obtain a partition algorithm for arbitrary graphs of size n that builds a spanning forest in time O ( log n ) with probability 1 - o ( n - 1 ). We study some parameters such as the number, the size and the radius of trees of the spanning forest.

Details DOI
v2026.09.13