Geodesic
Election algorithms with random delays in trees
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2009_special_256_a2,
     author = {Marckert, Jean-Fran\c{c}ois and Saheb-Djahromi, Nasser and Zemmari, Akka},
     title = {Election algorithms with random delays in trees},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)},
     year = {2009},
     doi = {10.46298/dmtcs.2680},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2680/}
}
TY  - JOUR
AU  - Marckert, Jean-François
AU  - Saheb-Djahromi, Nasser
AU  - Zemmari, Akka
TI  - Election algorithms with random delays in trees
JO  - Discrete mathematics & theoretical computer science
PY  - 2009
VL  - DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2680/
DO  - 10.46298/dmtcs.2680
LA  - en
ID  - DMTCS_2009_special_256_a2
ER  - 
%0 Journal Article
%A Marckert, Jean-François
%A Saheb-Djahromi, Nasser
%A Zemmari, Akka
%T Election algorithms with random delays in trees
%J Discrete mathematics & theoretical computer science
%D 2009
%V DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2680/
%R 10.46298/dmtcs.2680
%G en
%F DMTCS_2009_special_256_a2
Marckert, Jean-François; Saheb-Djahromi, Nasser; Zemmari, Akka. Election algorithms with random delays in trees. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009). doi : 10.46298/dmtcs.2680. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2680/

Cité par Sources :