Gossip-based peer sampling in Social overlays
Independent thesis Advanced level (degree of Master (Two Years)), 30 credits / 45 HE creditsStudent thesis
Performance of many P2P systems depends on the ability to construct a ran-dom overlay network among the nodes. Current state-of-the-art techniques forconstructing random overlays have an implicit requirement that any two nodesin the system should always be able to communicate and establish a link be-tween them. However, this is not the case in some of the environments wheredistributed systems are required to be deployed, e.g, Decentralized Online So-cial Networks, Wireless networks, or networks with limited connectivity becauseof NATs/rewalls, etc. In such restricted networks, every node is able to com-municate with only a predened set of nodes and thus, the existing solutionsfor constructing random overlays are not applicable.In this thesis we propose agossip based peer sampling service capable of running on top of such restrictednetworks and producing an on-the-y random overlay. The service provides ev-ery participating node with a set of uniform random nodes from the network,as well as ecient routing paths for reaching those nodes via the restricted net-work. We perform extensive experiments on four real-world networks and showthat the resulting overlays rapidly converge to random overlays. The resultsalso exhibit that the constructed random overlays have self healing behaviourunder churn and catastrophic failures.
Place, publisher, year, edition, pages
Engineering and Technology
IdentifiersURN: urn:nbn:se:kth:diva-144417OAI: oai:DiVA.org:kth-144417DiVA: diva2:713473
Master of Science - Software Engineering of Distributed Systems