Uniformité d'un échantillonnage épidémique

Résumé : Au sein d'un ensemble de noeuds, un service d'échantillonnage aléatoire idéal se doit de retourner un pointeur vers un noeud, correspondant à un échantillon indépendant sans biais du groupe considéré. Cet article porte sur un service d'échantillonnage issue de la notion de mélange de vues. Chaque noeud possède une vision locale du système, constituée d'un ensemble de c pointeurs vers des noeuds. Afin d'implémenter correctement un service d'échantillonnage uniforme, cette vue pouvant évoluer au fil du temps, doit contenir un échantillon uniforme de taille c. Pour cela, des couples de noeuds échangent périodiquement une partie de leur vue locale (procédure de mélange). Cet article propose des résultats prouvés dans [BBB2009] que (i) à partir de n'importe quelle distribution des vues locales, après une série de mélanges suffisamment longue, chaque vue contiendra irrémédiablement un échantillon uniforme de taille c; (ii) une fois la propriété précédente vérifié, toute série de mélange consécutive ne modifiera pas la propriété d'uniformité et (iii) une borne inférieure de la vitesse de convergence.
Type de document :
Communication dans un congrès
Maria Gradinariu Potop-Butucaru and Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00475754
Contributeur : Yann Busnel <>
Soumis le : jeudi 22 avril 2010 - 18:54:51
Dernière modification le : vendredi 12 octobre 2018 - 15:10:02
Document(s) archivé(s) le : lundi 22 octobre 2012 - 15:21:02

Fichier

BBB10-Algotel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00475754, version 1

Collections

Citation

Yann Busnel, Roberto Beraldi, Roberto Baldoni. Uniformité d'un échantillonnage épidémique. Maria Gradinariu Potop-Butucaru and Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010. 〈inria-00475754〉

Partager

Métriques

Consultations de la notice

112

Téléchargements de fichiers

142