Evènement pour le groupe Algorithmique Distribuée


Date 2013-01-14  14:00-15:00
TitreTwo 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  
LieuSalla 178 
OrateurAkka Zemmari 
UrlLabri 



Aucun document lié à cet événement.

Retour
Retour à l'index