Asymptotically Optimal Randomized Tree Embedding in Static Networks

The problem of dynamic tree embedding in static networks is studied in this paper. We 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, we 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. Our analysis technique is based on random walks on static networks. Hence, analytical expressions for expected load on all the processors are available. Keywords: Asymptotic performance, dynamic load distribution, hypercube, mesh, randomized tree embedding, static network, torus. 1 Introduction Many parallel computations are tree structured. Examples are divide-and-conquer algorithms, backtrack search algorithms, branch-and-..