Characterizing the Adversarial Power in Uniform and Ergodic Node Sampling

Emmanuelle Anceaume 1 Yann Busnel 2 Sébastien Gambs 1
1 ADEPT - Algorithms for Dynamic Dependable Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : In this paper, we consider the problem of achieving uniform and ergodic peer sampling in large scale dynamic systems under adversarial behaviors. The main challenge is to guar- antee that any honest node is able to construct a uniform and non-fixed (ergodic) sample of the node identifiers in the system, and this, despite the presence of malicious nodes controlled by an adversary. This sample is built out of a stream of events received at each node. We consider and study two types of adversary: an omniscient adversary that has the capacity to eavesdrop all the messages that are ex- changed within the system, and a blind adversary that can only observe messages that have been sent or received by the manipulated nodes. The former model allows us to derive lower bounds on the impact that the adversary has on the sampling functionality while the latter one corresponds to a realistic model. Given any sampling strategy, we quantify the minimum effort exerted by both types of adversary on any input stream to prevent this strategy from outputting a uniform and ergodic sample.
Keywords : Theory Algorithms
Type de document :
Communication dans un congrès
The 1st International Workshop on Algorithms and Models for Distributed Event Processing (AlMoDEP '11) collocated with the 25th International Symposium on Distributed Computing (DISC 2011), Sep 2011, Rome, Italy. ACM, 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00617866
Contributeur : Yann Busnel <>
Soumis le : mardi 30 août 2011 - 16:32:59
Dernière modification le : mercredi 16 mai 2018 - 11:23:01
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 20:44:26

Fichier

ABG11-ALMODEP.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00617866, version 1

Citation

Emmanuelle Anceaume, Yann Busnel, Sébastien Gambs. Characterizing the Adversarial Power in Uniform and Ergodic Node Sampling. The 1st International Workshop on Algorithms and Models for Distributed Event Processing (AlMoDEP '11) collocated with the 25th International Symposium on Distributed Computing (DISC 2011), Sep 2011, Rome, Italy. ACM, 2011. 〈inria-00617866〉

Partager

Métriques

Consultations de la notice

1194

Téléchargements de fichiers

151