Thicket: A Protocol for Building and Maintaining Multiple Trees in a P2P Overlay.
M. Ferreira, J. Leitão, and L. Rodrigues.
Selected sections of this report were published in the proceedings of
the 29th IEEE Symposium on Reliable Distributed Systems (SRDS), New
Delhi, India, 31 October-3 November 2010.
One way to efficiently disseminate information in a P2P overlay is
to rely on a spanning tree. However, in a tree, interior nodes
support a much higher load than leaf nodes. Also, the failure of a
single node can break the tree, impairing the reliability
of the dissemination protocol. These problems can be addressed by
using multiple trees, such that each node is interior in just a few
trees and a leaf node in the remaining; the multiple trees allow to
achieve load distribution and also to send redundant information for
fault-tolerance. This paper proposes Thicket, a decentralized
algorithm to efficiently build and maintain such multiple trees over
a single unstructured overlay network. The algorithm has been
implemented and is extensively evaluated using simulation in a P2P
overlay with 10.000 nodes.
Also available extended report (pdf)