On Social Overlays and Their Application to Decentralized Online Social Networks

Over the last decade, Online Social Networks (OSNs) have attracted hundreds of millions of users worldwide, establishing themselves as one of most successful communication tools to date. Yet, the business model adopted by current centralized approaches makes them inherently prone to privacy issues and hostile to openness, as service providers rely on the commercial exploitation of their userbases' private data as their means of survival. We believe, as others do, that decentralization could represent a solution to this fundamental problem. In this work, we propose a novel P2P approach to decentralized OSNs in which peers are organized as a social overlay (SO): an overlay network that effectively mirrors an underlying social network by constraining communication to pairs of peers whose owners are friends. SOs are special in two ways. First, by embodying friendship in their links, SOs can help us either solve or mitigate fundamental trust-related issues that arise in P2P systems. Second, SOs exhibit an inherent compatibility towards OSNs, a result of the former being shaped after human communication, and the latter being human communication tools. These give raise to an inherent potential for synergy, which we propose to reap by means of a simple approach that provides a key functionality of modern OSNs: profile-based communication. In our approach, nodes cache the profile pages of their friends locally, and updates get proactively disseminated only by trusted nodes, over a user's ego network: the subgraphs of social networks composed by a user, her friends, and the connections among them. The contributions of this thesis then emerge as we tackle this seemingly simple problem of update dissemination over ego networks and, along the way, uncover issues that lead us to progressively deeper problems and understanding, and, ultimately, to effective solutions. In the first part of this thesis, we explore the use of push gossip protocols as the means to achieve efficient dissemination of updates over ego networks. We show that mainstream gossip protocols cannot be applied in this context, due to the largely non-uniform structure of ego networks. By taking these structural properties into account, we develop a novel gossip protocol that is able to adapt to, and leverage this non-uniformity, providing efficient and timely dissemination of updates. The study of these dissemination protocols under peer churn leads us to uncover the second problem we tackle in this thesis -- namely, the network-induced communication delays that emerge from the interaction of the social graph with the underlying peer dynamics. By means of a small-scale simulation study, we find that not only these delays can be rather extreme, but that they matter more than the underlying dissemination protocol on the long run. While this realization is in itself a contribution, we also find that evaluating the problem in more depth, as well as identifying opportunities for improvement, cannot be done by simulations alone. This is due to three factors: i) the size of the target networks under study, ii) the large parameter space inherent to availability modelling, and iii) the large number of repetitions required for obtaining good quality estimators. Put together, these translate into prohibitive costs. We therefore propose a novel hybrid analytical/simulation framework that enables the estimation of dissemination delays at a practical cost. In the third part of this thesis, we show how to further develop this framework by deriving analytical, closed-form expressions that describe delays as a function of a graph and availability parameters, when the underlying availability model is based on a certain class of simpler distributions. Finally, by putting together the lessons we learnt along the way -- our dissemination protocol and the knowledge we acquired about the workings of communication delays -- we devise the final contribution of this thesis: a hybrid, cloud-assisted P2P architecture that enables efficient dissemination in social overlays under churn. This solution, as we show, provides performance that rivals that of centralized solutions, while incurring modest economical costs.