Determining the expected load of dynamic tree embeddings in hypercubes

The main contribution of this paper is to use recurrence relations in analyzing the performance of a dynamic tree embedding algorithm in hypercubes. These recurrence relations characterize the expected load on each processor in a randomized tree embedding, and enable us to evaluate expected loads numerically and analytically. As a matter of fact, our methodology does not depend on the hypercube topology, and can be applied to study dynamic tree growing in other networks.