Asymptotically optimal randomized tree embedding in static networks

The problem of dynamic tree embedding in static networks is studied. The authors provide a unified framework for studying the performance of randomized tree embedding algorithms which allow a newly created tree node to take a random walk of a short distance to reach a processor nearby. In particular, they propose simple randomized algorithms on several most common and important static networks, including d-dimensional meshes, d-dimensional tori, and hypercubes. It is shown that these algorithms, which have a small constant dilation, are asymptotically optimal. The analysis technique is based on random walks on static networks. Hence, analytical expressions for expected load on all the processors are available