TY - JOUR

T1 - Performance Analysis for Dynamic Tree Embedding ink-Partite Networks by a Random Walk

AU - Shen, Hong

AU - Li, K.

AU - Pan, Y.

AU - Young, G. H.

AU - Zheng, S. Q.

N1 - Funding Information:
This research project was supported by the following research grants: The Australian Research Council under its Large Research Grant (1996–98) A849602031 (for H. Shen); the National Science Foundation under Grant ECS-9626215 and Louisiana Grant LEQSF (1996–99)-RD-A-16 (for S. Q. Zheng); National Aeronautics and Space Administration and the State University of New York through the NASA/University Joint Venture (JOVE) Program between National Aeronautics and Space Administration and the State University of New York and the 1996 NASA/ASEE Summer Faculty Fellowship Program (for K. Li); the National Science Foundation under Grant CCR-9540901, the Air Force Avionics Laboratory Grant F33615-C-2218, and a Summer Research Fellowship from the University of Dayton Research Council (for Y. Pan); and CUHK Grant 220501290 (for G. Young).

PY - 1998/4/10

Y1 - 1998/4/10

N2 - We study the problem of dynamic tree embedding ink-partite networksGkand analyze the performance on interpartition load distribution of the embedding. We show that, for ring-connectedGk, if the embedding proceeds by taking a unidirectional random walk at a length randomly chosen from [0, Δ - 1], where Δ is a multiple ofk, the best-case performance is achievable at probability2πke-k, which is much higher than the asymptotically zero probability at which the worst-case performance may appear. We also show that the same probabilities hold for fully connectedGkif the embedding proceeds by taking a random walk at a length randomly chosen from [2, ∞). Whenk= 2 (bipartite networks), our results show that if we do the embedding under the above random-walk schemes in their corresponding networks, we will have a 50% chance to achieve the best-case performance. We also analyze the performances for embedding in these networks in the expected case and observe the interesting fact that they match the performances in the best case when the network isk-partitionable into partitions of equal size.

AB - We study the problem of dynamic tree embedding ink-partite networksGkand analyze the performance on interpartition load distribution of the embedding. We show that, for ring-connectedGk, if the embedding proceeds by taking a unidirectional random walk at a length randomly chosen from [0, Δ - 1], where Δ is a multiple ofk, the best-case performance is achievable at probability2πke-k, which is much higher than the asymptotically zero probability at which the worst-case performance may appear. We also show that the same probabilities hold for fully connectedGkif the embedding proceeds by taking a random walk at a length randomly chosen from [2, ∞). Whenk= 2 (bipartite networks), our results show that if we do the embedding under the above random-walk schemes in their corresponding networks, we will have a 50% chance to achieve the best-case performance. We also analyze the performances for embedding in these networks in the expected case and observe the interesting fact that they match the performances in the best case when the network isk-partitionable into partitions of equal size.

UR - http://www.scopus.com/inward/record.url?scp=0040758090&partnerID=8YFLogxK

U2 - 10.1006/jpdc.1998.1440

DO - 10.1006/jpdc.1998.1440

M3 - Article

AN - SCOPUS:0040758090

SN - 0743-7315

VL - 50

SP - 144

EP - 156

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 1-2

ER -