Detecting heavy-hitters in a P2P network

        Zbigniew Golebiewski,  Miroslaw Kutylowski,  Filip Zagorski
           Institute of Mathematics and Computer Science, 
                Wroclaw University of Technology
                       Jaroslaw Kutylowski
           Heinz Nixdorf-Institut, Universitaet Paderborn

We consider the problem of unfair use of distributed  information systems
based on P2P technology. A fair user states a limited number of queries
not only to a single node but also to the system as a whole. A user is 
considered to be unfair if  he  state queries to a substantial fraction 
of the nodes of the system. Such a node is called \emph{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 between  nodes of a P2P network. The algorithm proposed in this paper
is well suited for a P2P network in the sense that it requires no central 
coordination and decision making. It is also immune against an adversary 
controlling some number of nodes in the P2P network, or disrupting some 
connections between nodes. 

* IFIP 1st International Conference on Network and Service Security (N2S)

This work was partially supported by EU within
the 6th Framework Programme under contract 001907 (DELIS), 
MNiSZW grants N206 1842 33