On the Power of the Adversary to Solve the Node Sampling Problem

Emmanuelle Anceaume 1, 2 Yann Busnel 3 Sébastien Gambs 2
1 CIDER
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
2 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
3 GDD - Gestion de Données Distribuées [Nantes]
LINA - Laboratoire d'Informatique de Nantes Atlantique
Abstract : We study the problem of achieving uniform and fresh peer sampling in large scale dynamic systems under adversarial behaviors. Briefly, uniform and fresh peer sampling guarantees that any node in the system is equally likely to appear as a sample at any non malicious node in the system and that infinitely often any node has a non-null probability to appear as a sample of honest nodes. This sample is built locally out of a stream of node identifiers received at each node. An important issue that seriously hampers the feasibility of node sampling in open and large scale systems is the unavoidable presence of malicious nodes. The objective of malicious nodes mainly consists in continuously and largely biasing the input data stream out of which samples are obtained, to prevent (honest) nodes from being selected as samples. First we demonstrate that restricting the number of requests that malicious nodes can issue and providing a full knowledge of the composition of the system is a necessary and sufficient condition to guarantee uniform and fresh sampling. We also define and study two types of adversary models: 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 nodes it controls. 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 more realistic setting. Given any sampling strategy, we quantify the minimum effort exerted by both types of adversary on any input stream to prevent this sampling strategy from outputting a uniform and fresh sample.
Keywords : Data Stream Kullback-Leibler Divergence Uniform sampling Freshness Byzantine adversary
Document type :
Journal articles
Complete list of metadatas

Cited literature [38 references]  Display  Hide  Download
https://hal.archives-ouvertes.fr/hal-00926485
Contributor : Yann Busnel <>
Submitted on : Thursday, January 9, 2014 - 4:18:15 PM
Last modification on : Friday, July 26, 2019 - 1:32:08 PM
Long-term archiving on: Thursday, April 10, 2014 - 11:45:24 AM

File

abg-tldks2013.pdf
Files produced by the author(s)

Identifiers

Collections

UNIV-RENNES1 | CNRS | INRIA | IRISA | SUP_CIDRE | SUPELEC | UNIV-NANTES | LINA-GDD | LINA | INSTITUT-TELECOM | IRISA-D1 | UR1-UFR-ISTIC | UNIV-RENNES

Citation

Emmanuelle Anceaume, Yann Busnel, Sébastien Gambs. On the Power of the Adversary to Solve the Node Sampling Problem. Transactions on Large-Scale Data- and Knowledge-Centered Systems, Springer Berlin / Heidelberg, 2013, 8290, pp.102-126. ⟨10.1007/978-3-642-45269-7_5⟩. ⟨hal-00926485⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

2837

Files downloads

489

 

 

Contact

archive-ouverte@inria.fr