Evènement pour le groupe
Algorithmique Distribuée
Date | 2013-01-14 14:00-15:00 |
Titre | Two Monte-Carlo Election Algorithms for Anonymous Graphs without any Initial Knowledge |
Résumé | The paper proposes and analyses two Monte Carlo election algorithms for anonymous graphs without any initial knowledge. Both have a time complexity equal to $O(D)$, where $D$ is the diameter of the graph. The first is correct with probability $1-o(n^{-1})$ (where $n$ is the size of the graph). The size of messages is $O(log n)$ with probability $1-o(n^{-1})$ and the expected value of the size of messages is also $O(log n)$. The second is correct with probability $1-o(n^{-c})$ for any $cgeq 1$. The size of messages is $Oleft((log n)(log^* n)^2
ight)$ with probability $1-o(n^{-c})$ for any $cgeq 1$; their expected size is $Oleft((log n)(log^* n)
ight)$.
This is a joint work with Y. Métivier and J. M. Robson |
Lieu | Salla 178 |
Orateur | Akka Zemmari |
Url | Labri |
Aucun document lié à cet événement.
RetourRetour à l'index