Balanced-Replication Algorithms for Distribution Trees
Edith Cohen, Haim Y. Kaplan · SIAM Journal on Computing · 2004
In many Internet applications, requests for a certain object are routed bottom-up over a tree where the root of the tree is the node containing the object. When an object becomes popular, the root node of the tree may become a hot-spot. Therefore, many applications allow intermediate nodes to acquire the ability to serve the requests, for example, by caching the object. We call such distinguished nodes primed. We propose and analyze different algorithms where nodes decide when to become primed; these algorithms balance the maximum load on a node and the number of primed nodes. Many applications require both fully distributed decisions and smooth convergence to a stable set of primed nodes. We first present optimal algorithms which require communication across the tree. We then consider the natural previously proposed {\sc threshold} algorithm, where a node becomes primed when the incoming flow of requests exceeds a threshold. We show examples where {\sc threshold} exhibits undesirable behavior during convergence. Finally, we propose another fully distributed algorithm, {\sc gap}, which converges gracefully.