A dynamic coalition formation game for search efficient adaptive overlay construction in unstructured peer-to-peer networks

A great number of recent works deal with improving search in peer-to-peer systems, specifically by clustering peers into semantic groups. When the process of clustering is predetermined and static, it suffers from lack of adaptation to highly dynamic peer-to-peer environments. We model the problem as a non-superadditive coalition game with non-transferable utility characteristic function, and propose a distributed dynamic coalition formation algorithm through myopic best-reply with experiment rule to solve the coalition formation problem. Coalitions are formed by peers with similar interests considering geographical proximity. The overlay network is dynamically reconfigured over time based on the changes in the interests or locations of the individual peers. The convergence of the proposed algorithm using “core solution” concept is studied. The simulation results show that the proposed algorithm can efficiently reduce the search time, although the overhead of the overlay adaptation is slightly higher.