We consider networks of processes which interact with beeps. Various beeping models are used. The basic one, defined by Cornejo and Kuhn [CK10], assumes that a process can choose either to beep or to listen; if it listens it can distinguish between silence or the presence of at least one beep. The aim of this paper is the study of the resolution of paradigms such as collision detection, computation of the degree of a vertex, colouring, or 2-hop-colouring in the framework of beeping models. For each of these problems we present Las Vegas or Monte Carlo algorithms and we analyse their complexities expressed in terms of the number of slots. We present also efficient randomised emulations of more powerful beeping models on the basic one. We illustrate emulation procedures with an efficient degree computation algorithm in the basic beeping model; this algorithm was given initially in a more powerful model.
In the model of point to point message passing, vertex colouring is mainly studied under two assumptions: - vertices have unique identifiers, and more generally, they have an initial colouring, - every vertex has the same initial state and initially only knows its own edges. If vertices have an initial colour, Kuhn and Wattenhofer @cite_19 have obtained efficient time complexity algorithms to obtain @math colours in the case where every vertex can only send its own current colour to all its neighbours. In @cite_33 , Johansson analyses a simple randomised distributed vertex colouring algorithm for anonymous graphs. He proves that this algorithm runs in @math rounds w.h.p. on graphs of size @math The size of each message is @math thus the bit complexity per channel of this algorithm is @math @cite_36 presents an optimal bit and time complexity Las Vegas distributed algorithm for colouring any anonymous graph in @math bit rounds w.h.p.
@cite_36 @cite_19 @cite_33
2062111496 2737338020 2121696574 2065826935
We present and analyse a very simple randomised distributed vertex colouring algorithm for arbitrary graphs of size n that halts in time O(logn) with probability 1-o(n^-^1). Each message containing 1 bit, its bit complexity per channel is O(logn). From this algorithm, we deduce and analyse a randomised distributed vertex colouring algorithm for arbitrary graphs of maximum degree @D and size n that uses at most @D+1 colours and halts in time O(logn) 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(logn) 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. We present a randomised distributed maximal independent set (MIS) algorithm for arbitrary graphs of size @math that halts in time @math with probability @math , each message containing @math bit: thus its bit complexity per channel is @math (the bit complexity is the number of bits we need to solve a distributed task, it measures the communication complexity). We assume that the graph is anonymous: unique identities are not available to distinguish the processes; we only assume that each vertex distinguishes between its neighbours by locally known channel names. Furthermore we do not assume that the size (or an upper bound on the size) of the graph is known. This algorithm is optimal (modulo a multiplicative constant) for the bit complexity and improves the best previous randomised distributed MIS algorithms (deduced from the randomised PRAM algorithm due to Luby) for general graphs which is @math per channel (it halts in time @math and the size of each message is @math ). This result is based on a powerful and general technique for converting unrealistic exchanges of messages containing real numbers drawn at random on each vertex of a network into exchanges of bits. Then we consider a natural question: what is the impact of a vertex inclusion in the MIS on distant vertices? We prove that this impact vanishes rapidly as the distance grows for bounded-degree vertices. We provide a counter-example that shows this result does not hold in general. We prove also that these results remain valid for Luby's algorithm presented by Lynch and by Wattenhofer. This question remains open for the variant given by Peleg. Suppose in a graph G vertices can be either red or blue. Let k be odd. At each time step, each vertex v in G polls k random neighbours and takes the majority colour. If it does not have k neighbours, it simply polls all of them, or all less one if the degree of v is even. We study this protocol on graphs of a given degree sequence, in the following setting: initially each vertex of G is red independently with probability α < 1 2 , and is otherwise blue. We show that if α is sufficiently biased, then with high probability consensus is reached on the initial global majority within O ( log k log k n ) steps if 5 ? k ? d , and O ( log d log d n ) steps if k d . Here, d ? 5 is the effective minimum degree, the smallest integer which occurs ? ( n ) times in the degree sequence. We further show that on such graphs, any local protocol in which a vertex does not change colour if all its neighbours have that same colour, takes time at least ? ( log d log d n ) , with high probability. Additionally, we demonstrate how the technique for the above sparse graphs can be applied in a straightforward manner to get bounds for the Erd?s-Renyi random graphs in the connected regime. Consider an n-vertex graph G = (V, E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, that is, it proceeds in discrete rounds. In the distributed vertex coloring problem, the objective is to color G with Δ + 1, or slightly more than Δ + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time.) Efficient randomized algorithms for this problem are known for more than twenty years [ 1986; Luby 1986]. Specifically, these algorithms produce a (Δ + 1)-coloring within O(log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O(Δ2) colors. This algorithm was devised in a seminal FOCS’87 paper by Linial [1987]. Its running time is O(log* n). In the same article, Linial asked whether one can color with significantly less than Δ2 colors in deterministic polylogarithmic time. By now, this question of Linial became one of the most central long-standing open questions in this area. In this article, we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ1+o(1) colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O(f(Δ)log Δ log n), for an arbitrarily slow-growing function f(Δ) = ω(1). We can also produce an O(Δ1+η)-coloring in O(log Δ log n)-time, for an arbitrarily small constant η > 0, and an O(Δ)-coloring in O(Δe log n) time, for an arbitrarily small constant e > 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity a, our algorithm produces an O(a1+η)-coloring, for an arbitrarily small constant η > 0, in time O(log a log n).