Secure Peer Sampling

Gossiping has been identified as a useful building block for the development of large-scale, decentralized collaborative systems. With gossiping, individual nodes periodically interact with random partners, exchanging information about their local state; yet, they may globally provide several useful services, such as information diffusion, topology management, monitoring, load-balancing, etc. One fundamental building block for developing gossip protocols is peer sampling, which provides nodes with the ability to sample the entire population of nodes in order to randomly select a gossip partner. In existing implementations, however, one fundamental aspect is neglected: security. Byzantine nodes may subvert the peer sampling service and bias the random selection process, for example, by increasing the probability that a fellow malicious node is selected instead of a random one. The contribution of this paper is an extension to existing peer sampling protocols with a detection mechanism that identifies and blacklists nodes that are suspected of behaving maliciously. An extensive experimental evaluation shows that our extension is efficient in dealing with a large number of malicious nodes. © 2010 Elsevier B.V. All rights reserved.