Election algorithms with random delays in trees

Abstract : 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.
Type de document :
Communication dans un congrès
Krattenthaler, Christian and Strehl, Volker and Kauers, Manuel. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), pp.611-622, 2009, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185372
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 11:06:17
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:02:04

Fichier

dmAK0151.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185372, version 1

Collections

Citation

Jean-François Marckert, Nasser Saheb-Djahromi, Akka Zemmari. Election algorithms with random delays in trees. Krattenthaler, Christian and Strehl, Volker and Kauers, Manuel. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), pp.611-622, 2009, DMTCS Proceedings. 〈hal-01185372〉

Partager

Métriques

Consultations de la notice

294

Téléchargements de fichiers

123