Piggyback game: Efficient event stream dissemination in Online Social Network systems

摘要

Event stream dissemination dominates the workloads in large-scale Online Social Network (OSN) systems. Based on the de facto per-user view data storage, event stream dissemination raises a large amount of inter-server traffics due to the complex interconnection among OSN users. The state-of-the-art schemes mainly explore the structure features of social graphs to reduce the inter-server messages for event stream dissemination. Different sub-graph structures are exploited for achieving the approximated optimal assignment. However, such schemes incur high costs of computation or communication. In this work, we follow a different design philosophy by using a game theoretic approach, which decomposes the high complex graph computation problem into individuals' rational strategy selection of each node. Specifically, we propose a novel social piggyback game to achieve a more efficient solution. We mathematically prove the existing of the Nash Equilibrium of the social piggyback game. Moreover, we propose an efficient best response dynamic algorithm to achieve the Nash Equilibrium, which quickly converges in a small number of iterations for large-scale OSNs. We further show that the communication cost of this design achieves a 1.5-approximation of the theoretical social optimal. We conduct comprehensive experiments to evaluate the performance of this design using large-scale real-world traces from popular OSN systems. Results show that the social piggyback game achieves a significant 302× improvement in system efficiency compared to existing schemes.