Optimizing cluster formation in super-peer networks via local incentive design

A super-peer based overlay network architecture for peer-to-peer (P2P) systems allows for some nodes, known as the super-peers, that are more resource-endowed than others, to assume a higher share of workload. Ordinary peers are connected to the super-peers and rely on them for their transactional needs. Many criteria for a peer to choose its super-peer have been explored, some of them based on physical proximity, semantic proximity, or by purely random choice. In this paper, we propose an incentive-based criterion that uses semantic similarities between the content interests of the peers and, at the same time, encourages even load distribution across the super-peers. The incentive is achieved via a game theoretic framework that considers each peer as a rational player, allowing stable Nash equilibria to exist and hence guarantees a fixed point in the strategy space of the peers. This guarantees convergence (assuming static network parameters) to a locally optimal assignment of peers to super-peers with respect to a global cost that approximates the average query resolution time. We also show empirically that the local cost framework that we employ performs closely to (and in some cases better than) a similar scheme based on the formulation of a centralized cost function that requires the peers to know an additional global parameter.