Detecting heavy-hitters in a P2P network

摘要

We consider the problem of unfair use of distributed information systems such as P2P networks. A fair user states a limited number of queries or requests not only to a single node but also to the system as a whole. A user is considered to be unfair if he floods the system, i.e. states queries to a substantial fraction of the nodes of the system. Such a node is called a heavy hitter. We design an randomized algorithm that can be used to detect heavy hitters. Our solution is focused on communication efficiency - our goal is to detect the heavy hitters without exchanging the full information about the users' activity by the nodes of the network. The algorithm proposed in this paper is well suited for systems with no no central coordination and decision making, such as P2P networks. It is also immune against an adversary controlling some number of nodes or disrupting some connections between them.