Characterizing the Adversarial Power in Uniform and Ergodic Peer 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 : We consider the problem of achieving uniform and ergodic peer sampling in large scale open systems under adversarial behavior. The main challenge is to guarantee that any honest peer is able to construct a uniform and non-denitive (ergodic) sample of the peers identiers in the system, and this even in the presence of Byzantine peers controlled by the adversary. This sample is built out of a stream of peer identiers received at each node. We consider and study two types of adversary; an omniscient adversary that has the capacity to eavesdrop on all the messages that are exchanged within the system, and a blind adversary that can only observe messages that have been sent or received by peers he controls. In both models, the adversary can disrupt the input stream by injecting new messages or dropping messages sent by honest peers. Given any sampling strategy, we quantify the minimum eort an adversary has to exert on any input stream to prevent the sampling strategy from outputting a uniform and ergodic sample. We derive lower bounds for both adversary models.
Type de document :
[Research Report] PI-1966, 2011, pp.15
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Ist Rennes <>
Soumis le : mardi 8 février 2011 - 15:38:42
Dernière modification le : vendredi 16 novembre 2018 - 01:22:00
Document(s) archivé(s) le : lundi 9 mai 2011 - 03:15:57


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00564293, version 1


Emmanuelle Anceaume, Yann Busnel, Sébastien Gambs. Characterizing the Adversarial Power in Uniform and Ergodic Peer Sampling. [Research Report] PI-1966, 2011, pp.15. 〈inria-00564293〉



Consultations de la notice


Téléchargements de fichiers