| Abstract |
|---|
| This paper analyzes simple randomized load distribution algorithms thatdynamically embed arbitrary trees in a distributed network with an arbitrarytopology. We model a load distribution algorithm by an associetedMarkov chain and we obtain the following result~: a given randomizedload distribution algorithm spreads any M-node tree in a distributednetwork with N vertices with load (i.e., the maximum number of nodesmapped on a single vertex) $O(\frac{M}{N} + \delta(\varepsilon))$,where $\delta(\varepsilon)$ depends on the convergence rate of theassociated Markov chain. Experimental results obtained by the implementationof these load distribution algorithms, to validate our framework,on the two-dimensional mesh of the massively parallel computer MasPar MP-1with 16,384 processors, and on a network of workstations are also given. |
| Contact |
| J.Gaber LIFL - Bat. M3 -,USTL59655,Villeneuve d'Ascq cedex,France gaber@lifl.fr |