Skip to Main content Skip to Navigation
Journal articles

Byzantine-tolerant Uniform Node Sampling Service in Large-scale Networks

Emmanuelle Anceaume 1 Yann Busnel 2, 3 Bruno Sericola 3 
1 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
3 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Abstract : We consider the problem of achieving uniform node sampling in large scale systems in presence of Byzantine nodes. The uniform node sampling service offers to applications using it a single simple primitive that returns, upon invocation, the identifier of a random node that belongs to the system. We first propose an omniscient strategy that processes on the fly an unbounded and arbitrarily biased input stream made of node identifiers exchanged within the system, and outputs a stream that preserves the uniformity property. Informally, uniformity states that any node in the system should have the same probability to appear in the sample of any correct node of the system. We show through a Markov chain analysis that this property holds despite any arbitrary bias introduced by the adversary. We then propose a strategy based on a sketch data structure that is capable of approximating the omniscient strategy without requiring any prior knowledge on the composition of the input stream. We show through both theoretical analysis and extensive simulations that this "knowledge-free" strategy accurately approximates the omniscient one. We evaluate the resilience of the knowledge-free strategy by studying two representative attacks (flooding and targeted attacks). We quantify the minimum number of identifiers that Byzantine nodes must insert in the input stream to prevent uniformity. Finally, we propose a new construction that processes each input stream with sketches put in series that allows to both increase the accuracy of a single sketch and decrease the time to converge to a uniform output stream. To our knowledge, such a work has never been proposed before.
Complete list of metadata
Contributor : Yann Busnel Connect in order to contact the contributor
Submitted on : Monday, June 21, 2021 - 9:39:16 AM
Last modification on : Friday, August 5, 2022 - 2:54:52 PM
Long-term archiving on: : Wednesday, September 22, 2021 - 6:11:56 PM


Files produced by the author(s)



Emmanuelle Anceaume, Yann Busnel, Bruno Sericola. Byzantine-tolerant Uniform Node Sampling Service in Large-scale Networks. International Journal of Parallel, Emergent and Distributed Systems, Taylor & Francis, 2021, 36 (5), pp.1-28. ⟨10.1080/17445760.2021.1939873⟩. ⟨hal-03265593⟩



Record views


Files downloads