X-BOT: A Protocol for Resilient Optimization of Unstructured Overlays
J. Leitão, J. P. Marques, J. Pereira and L. Rodrigues
Selected sections of this report were published in the Proceedings of
the 28th IEEE International Symposium on Reliable Distributed Systems,
Niagara Falls, New York, U.S.A., Sep, 2009.
Abstract
Gossip, or epidemic, protocols have emerged as a highly scalable and
resilient approach to implement several application level services
such as reliable multicast, data aggregation, publish-subscribe,
among others. All these protocols organize nodes in an unstructured
random overlay network. In many cases, it is interesting to bias the
random overlay in order to optimize some efficiency criteria, for
instance, to reduce the stretch of the overlay routing. In this paper
we propose X-Bot, a new protocol that allows to bias the topology of
an unstructured gossip overlay network. X-Bot is completely
decentralized and, unlike previous approaches, preserves several key
properties of the original (non-biased) overlay (most notably, the
node degree and consequently, the overlay connectivity). Experimental
results show that X-Bot can generate more efficient overlays than
previous approaches.
Also available extended report (pdf)
Luís Rodrigues