Seminario Interdipartimentale di Algoritmica
 
 

DI - Department of Computer Science, via Salaria 113
Seminar Room, third floor

Abstract:
Overlay topology, as defined by the ``who knows whom'' relation is a key concept in distributed systems, with many applications. For example, properties of the communication topology (that defines who can send messages to whom) play a crucial role in determining the performance of function like search, routing or key lookup. Scalability and reliability are also determined by topology. The ``who knows whom'' relation has other uses as well. It can express sorting, where nodes know the other nodes that precede or follow them in some ordering defined over the nodes. Topology can also express clustering, network proximity, or solutions to search problems where requets are connected to the sources of information. Motivated by this generality and importance of topology management, in the present talk we describe scalable, reliable and extremely simple gossip protocols to create several overlay topologies, inluding random (unstructured) and structured ones (ring, torus, binary tree). Our protocol scheme, called T-Man, can construct a large class of topologies that are defined by a single ranking function that orders nodes according to preference from any fixed base node. As will be demonstrated, with the appropriate selection of ranking function T-Man can sort a set of numbers or arrange them in different clustered or connected topologies.