5 papers · 1 filter
Convergence of some leader election algorithms
Svante Janson, Christian Lavault, Guy Louchard
We start with a set of n players. With some probability P(n,k), we kill n-k players; the other ones stay alive, and we repeat with them. What is the distribution of the number X_n…
Analysis of an Efficient Distributed Algorithm for Mutual Exclusion (Average-Case Analysis of Path Reversal)
Christian Lavault
The algorithm analysed by Naïmi, Trehe and Arnold was the very first distributed algorithm to solve the mutual exclusion problem in complete networks by using a dynamic logical tre…
Quasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots
Christian Lavault, Jean-François Marckert, Vlady Ravelomanana
A radio network (RN) is a distributed system consisting of radio stations. We design and analyze two distributed leader election protocols in RN where the number of radio s…
A distributed approximation algorithm for the minimum degree minimum weight spanning trees
Christian Lavault, Mario Valencia-Pabon
Fischer has shown how to compute a minimum weight spanning tree of degree at most in time for any constant , where $Δ^*…
Embeddings into the Pancake Interconnection Network
Christian Lavault
Owing to its nice properties, the pancake is one of the Cayley graphs that were proposed as alternatives to the hypercube for interconnecting processors in parallel computers. In t…