T-Man: Gossip-based Fast Overlay Topology Construction

Large-scale overlay networks have become crucial ingredients of fully-decentralized appli- cations and peer-to-peer systems. Depending on the task at hand, overlay networks are organized into different topologies, such as rings, trees, semantic and geographic proximity networks. We argue that the central role overlay networks play in decentralized applica- tion development requires a more systematic study and effort towards understanding the possibilities and limits of overlay network construction in its generality. Our contribu- tion in this paper is a gossip protocol called T-MAN that can build a wide range of overlay networks from scratch, relying only on minimal assumptions. The protocol is fast, robust, and very simple. It is also highly configurable as the desired topology itself is a parameter in the form of a ranking method that orders nodes according to preference for a base node to select them as neighbors. The paper presents extensive empirical analysis of the protocol along with theoretical analysis of certain aspects of its behavior. We also describe a prac- tical application of T-MAN for building CHORD distributed hash table overlays efficiently from scratch.