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 traffic 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 communications for event stream dissemination. Different sub-graph structures are exploited for achieving approximated optimal solutions. However, such schemes incur prohibitively high cost of either computation or communication. In this work, we follow a different design philosophy by using a game theoretic approach, which decomposes the highly complex graph computation problem into rational decision making of every individual social link. Specifically, we propose a novel social piggyback game to achieve a more efficient solution. We mathematically prove the existence 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 optimum. We conduct comprehensive experiments using large-scale real-world traces from popular OSN systems as well as implement a prototype system to evaluate the performance of this design. Results show that the social piggyback game achieves a significant 302x improvement in system efficiency compared to existing schemes.