• Characterizing the Adversarial...

Result: Characterizing the Adversarial Power in Uniform and Ergodic Node Sampling

Title:
Characterizing the Adversarial Power in Uniform and Ergodic Node Sampling
Authors:
Anceaume, Emmanuelle, Busnel, Yann, Gambs, Sébastien
Contributors:
Algorithms for Dynamic Dependable Systems (ADEPT), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-INRIA Rennes, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique de Nantes Atlantique (LINA), Mines Nantes (Mines Nantes)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)
Source:
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
Publisher Information:
CCSD; ACM, 2011.
Publication Year:
2011
Collection:
collection:SUPELEC
collection:UNIV-NANTES
collection:EC-PARIS
collection:UNIV-RENNES1
collection:CNRS
collection:INRIA
collection:INSA-RENNES
collection:INRIA-RENNES
collection:IRISA
collection:LINA
collection:LINA-GDD
collection:IRISA_SET
collection:SUP_CIDRE
collection:TESTALAIN1
collection:INRIA2
collection:UR1-HAL
collection:UR1-MATH-STIC
collection:LS2N
collection:UR1-UFR-ISTIC
collection:TEST-UNIV-RENNES
collection:TEST-UR-CSS
collection:UNIV-RENNES
collection:INRIA-RENGRE
collection:INSA-GROUPE
collection:UR1-MATH-NUM
collection:NANTES-UNIVERSITE
collection:UNIV-NANTES-AV2022
Subject Terms:
Theory, Algorithms, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, [INFO.INFO-DC]Computer Science [cs], Distributed, Parallel, and Cluster Computing [cs.DC]
Subject Geographic:
Rome, Italy
Original Identifier:
HAL:
Document Type:
Conference conferenceObject<br />Conference papers
Language:
English
Access URL:
https://inria.hal.science/inria-00617866
https://inria.hal.science/inria-00617866v1/document
https://inria.hal.science/inria-00617866v1/file/ABG11-ALMODEP.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00617866v1
Database:
HAL

Further Information

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.