Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/inria-00475754
Contributor : Yann Busnel Connect in order to contact the contributor
Submitted on : Thursday, April 22, 2010 - 6:54:51 PM
Last modification on : Wednesday, April 27, 2022 - 4:22:40 AM
Long-term archiving on: : Monday, October 22, 2012 - 3:21:02 PM

File

BBB10-Algotel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00475754, version 1

Collections

Citation

yann Busnel, Roberto Beraldi, Roberto Baldoni. Uniformité d'un échantillonnage épidémique. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. ⟨inria-00475754⟩

Share

Metrics

Record views

80

Files downloads

110