Election algorithms with random delays in trees
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2009-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2680/pdf |
| _version_ | 1827324058370310144 |
|---|---|
| author | Jean-François Marckert Nasser Saheb-Djahromi Akka Zemmari |
| author_facet | Jean-François Marckert Nasser Saheb-Djahromi Akka Zemmari |
| author_sort | Jean-François Marckert |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:02:42Z |
| format | Article |
| id | doaj.art-386a8456358d429f907946841051a216 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:02:42Z |
| publishDate | 2009-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-386a8456358d429f907946841051a2162024-03-07T14:45:40ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502009-01-01DMTCS Proceedings vol. AK,...Proceedings10.46298/dmtcs.26802680Election algorithms with random delays in treesJean-François Marckert0https://orcid.org/0000-0003-3773-262XNasser Saheb-Djahromi1Akka Zemmari2Laboratoire Bordelais de Recherche en InformatiqueLaboratoire Bordelais de Recherche en InformatiqueLaboratoire Bordelais de Recherche en InformatiqueThe 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.https://dmtcs.episciences.org/2680/pdfdistributed algorithmelection algorithmprobabilistic analysisrandom process[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Jean-François Marckert Nasser Saheb-Djahromi Akka Zemmari Election algorithms with random delays in trees Discrete Mathematics & Theoretical Computer Science 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] |
| title | Election algorithms with random delays in trees |
| title_full | Election algorithms with random delays in trees |
| title_fullStr | Election algorithms with random delays in trees |
| title_full_unstemmed | Election algorithms with random delays in trees |
| title_short | Election algorithms with random delays in trees |
| title_sort | election algorithms with random delays in trees |
| topic | 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] |
| url | https://dmtcs.episciences.org/2680/pdf |
| work_keys_str_mv | AT jeanfrancoismarckert electionalgorithmswithrandomdelaysintrees AT nassersahebdjahromi electionalgorithmswithrandomdelaysintrees AT akkazemmari electionalgorithmswithrandomdelaysintrees |