Jean-François Marckert ; Nasser Saheb-Djahromi ; Akka Zemmari - Election algorithms with random delays in trees

dmtcs:2680 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2680
Election algorithms with random delays in treesArticle

Authors: Jean-François Marckert ORCID1; Nasser Saheb-Djahromi 1; Akka Zemmari 1

  • 1 Laboratoire Bordelais de Recherche en Informatique

The election is a classical problem in distributed algorithmic. It aims to design and to analyze a distributed algorithm choosing a node in a graph, here, in a tree. In this paper, a class of randomized algorithms for the election is studied. The election amounts to removing leaves one by one until the tree is reduced to a unique node which is then elected. The algorithm assigns to each leaf a probability distribution (that may depends on the information transmitted by the eliminated nodes) used by the leaf to generate its remaining random lifetime. In the general case, the probability of each node to be elected is given. For two categories of algorithms, close formulas are provided.


Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
Keywords: Distributed Algorithm,Election Algorithm,Probabilistic Analysis,Random Process,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 267 times.
This article's PDF has been downloaded 217 times.