Election algorithms with random delays in trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2009

Election algorithms with random delays in trees

Résumé

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.
Fichier principal
Vignette du fichier
dmAK0151.pdf (247.08 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01185372 , version 1 (20-08-2015)

Identifiants

Citer

Jean-François Marckert, Nasser Saheb-Djahromi, Akka Zemmari. Election algorithms with random delays in trees. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.611-622, ⟨10.46298/dmtcs.2680⟩. ⟨hal-01185372⟩

Collections

CNRS TDS-MACS
236 Consultations
575 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More