Centaur: Dynamic message dissemination over online social networks

We present the design, implementation, and evaluation of Centaur, an application-level user-assisted message dissemination solution for Online Social Networks (OSN). Characteristics of OSNs make their message dissemination distinct from scenarios like multicast streaming and P2P file sharing. First, updates issued by each user are sporadic and the 'online' follower set is highly dynamic. Hence, it is unnecessarily expensive to maintain always-alive multicast topologies. Second, the key advantage of OSNs over traditional media is realtime update, which would be greatly shadowed if it takes long to construct well-shaped dissemination structures. Therefore, in contrast to the multitude of prior multicast solutions, Centaur constructs location-aware dissemination trees locally for each incoming message. We implement a prototype with Cirrus and evaluate it with Twitter data. Experiment results show that Centaur achieves 98% delivery ratio and few seconds of delay with only around one tenth server traffic compared to centralized solutions used in many current OSNs.