Service d'échantillonage uniforme résiliant aux comportments malveillants

International audienceNous proposons une solution au problème d'échantillonage uniforme dans les systèmes à grande échelle en présence de comportements byzantins. Notre premier algorithme permet d'uniformiser à la volée un flux de données (items) de taille non bornée, sous l'hypothèse que les probabilités exactes d'occurrence des items sont connues. Nous modélisons le comportement de notre algorithme par une chaîne de Markov dont nous étudions le régime stationnaire et le transitoire. Notre second algorithme relache l'hypothèse de connaissance de la probabilité d'occurrence des items dans le flux initial. Ces probabilités sont estimées à la volée en utilisant un espace mémoire logarithmique en la taille du flux. Nous évaluons la résilience de cet algorithme face à des attaques ciblées et par innondation. Nous quantifions l'effort que doit fournir l'adversaire (i.e., nombre d'items à injecter dans le flux initial) pour violer la propriété d'uniformité