Asymptotically optimal dynamic tree evolution by rapidly mixing random walks on regular networks

Tree-structured computations are among the most popular and important and powerful computing paradigms in computer science. In many such applications, the size and shape of a tree that represents a parallel computation is dynamic and unpredictable at compile time. The tree evolves gradually during the course of the computation. When such an application is executed on a multicomputer system with a static network, the dynamic tree evolution problem is to distribute the tree nodes to the processors of the network such that all the processors receive roughly the same amount of load and that communicating nodes are assigned to neighboring processors. The main contribution of the paper is to conduct a unified study of dynamic tree evolution on regular networks. Our regular networks include dd-dimensional torus networks, dd-dimensional lattice networks, complete dd-partite networks, and random regular networks. These networks include several fundamental networks such as rings, kk-ary dd-cubes, complete networks, and hypercubes as special cases. We describe a simple random-walk-based asymptotically optimal dynamic tree evolution algorithm on regular networks and analyze the exponential speed at which the performance ratio converges to the optimal. Our strategy is to prove that the Markov chain of a random walk on a regular network is rapidly mixing in the sense that, starting from any initial distribution, the Markov chain converges to its stationary distribution in a small number of steps. We also show that larger dilation results in better tree node distribution.