Practical Uniform Peer Sampling under Churn
Authors:
- Roberto BaldoniRBRoberto Baldoni
- Marco PlataniaMPMarco Platania
- Leonardo QuerzoniLQLeonardo Querzoni
- Sirio ScipioniSSSirio Scipioni
- 1 July 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23795352,p. 93-100
Abstract
Providing independent uniform samples from a system population poses considerable problems in highly dynamic settings, like P2P systems, where the number of participants and their unpredictable behavior (e.g., churn, crashes etc.) may introduce relevant bias. Current implementations of the Peer Sampling Service are designed to provide uniform samples only in static settings and do not consider that biased samples can directly affect the correctness of algorithms relying on a uniformity property or be exploited by a malicious adversary to increase the effectiveness of its attacks to the system. In this paper we provide a practical solution to the biasing problem by deploying a fully distributed Peer Sampling Correction Module on top of a given, possibly biased, peer sampling service. Samples provided by the peer sampling service will be locally processed by this module, using computationally efficient hashing functions, before getting to the application. The effectiveness of our approach is evaluated through an extensive simulation-based study.Keywords
This publication has 18 references indexed in Scilit:
- Practical Uniform Peer Sampling under Churn2010
- Brahms2008
- Identifying Malicious Peers Before It's Too Late: A Decentralized Secure Peer Sampling Service2007
- Distributed Uniform Sampling in Unstructured Peer-to-Peer Networks2006
- Lightweight probabilistic broadcastACM Transactions on Computer Systems, 2003
- Chord: a scalable peer-to-peer lookup protocol for internet applicationsIEEE/ACM Transactions on Networking, 2003
- Tolerating malicious gossipDistributed Computing, 2003
- On diffusing updates in a Byzantine environment2003
- Search and replication in unstructured peer-to-peer networks2002
- Min-Wise Independent PermutationsJournal of Computer and System Sciences, 2000