Arrow Research search

Author name cluster

J.M. Robson

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.

13 papers
1 author row

Possible papers

13

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

TCS Journal 2002 Journal Article

Constant bounds on the moments of the height of binary search trees

  • J.M. Robson

We show that binary search trees of a given size tend to have smaller height when the root division is into two subtrees of more balanced sizes. We deduce that the expectation of the absolute value of the difference in height of two binary search trees of the same number of nodes is less than 3. 135 infinitely often. We also deduce strong upper bounds on the probability of large deviations from the median. Putting together these two conclusions and a simple and plausible conjecture on critical nodes leads to O(1) bounds on all moments of binary search tree heights.

Details DOI

TCS Journal 1992 Journal Article

More languages of generalised star height 1

  • J.M. Robson

Suppose that membership of a word w in a language L is specified in terms of the number (modulo some integer k) of occurrences of a fixed word w′ as a factor of w. Then the language obtained for any m by adding arbitrary numbers of copies of am anywhere in the words of L has generalized star height at most 1.

Details DOI

TCS Journal 1991 Journal Article

An O(T log T) reduction from RAM computations to satisfiability

  • J.M. Robson

A new method is given for obtaining a boolean expression whose satisfiability is equivalent to the existence of an accepting computation of some nondeterministic machine. Although starting from random access machines, this method gives an expression of the same O(T log T) length as the best reduction from general Turing machines.

Details DOI

TCS Journal 1990 Journal Article

Strong time bounds: Non-computable bounds and a hierarchy theorem

  • J.M. Robson

A RAM program is said to run within a “strong” time bound T if on every sequence of n inputs it terminates within T(n) instruction executions. There are some programs whose execution time in this sense is a non-computable function of n. It is shown that such programs are essential in the sense that some functions can be computed within a non-computable time bound but not within any computable time bound. Nevertheless, strong time bounds are subject to a powerful hierarchy theorem. The condition such as being time constructable which normally applies to the “lower” function in such theorems is replaced by a condition of being the minimum strong time bound for some program.

Details DOI
v2026.09.13