Online social networks (OSNs) (e.g., Facebook, Twitter) are now among the most popular sites on the Web. An OSN provides a powerful means of establishing social connections and sharing, organizing, and finding content. For example, Facebook presently has over 500 million users. Unlike current file or video sharing systems (e.g., BitTorrent and YouTube), which are mainly organized around content, OSNs are organized around users. OSN users establish friendship relations with realworld friends or virtual friends, and post their profiles and content such as photos, videos, and notes to their personal pages. Video sharing has been an increasingly popular application in OSNs, enabling users to share their personal videos or interesting videos they found with their friends. The recent rapid development of OSN video sharing applications illustrates the evolution of OSNs from simply communication focused tools to a media portal. OSNs are transforming from a platform for catching up with friends to a venue for personal expression and for sharing a full variety of content and information. OSN’s further advancement is severely hindered by the intrinsic limits of the conventional client/server architecture of its video sharing system, which is not only costly in terms of server storage and bandwidth but also not scalable with the soaring amount of users and video content in OSNs.