A Caltech Library Service

Tight Bounds for On-line Tree Embedding

Bhatt, Sandeep and Greenberg, David and Leighton, Tom and Liu, Pangfeng (1991) Tight Bounds for On-line Tree Embedding. In: SODA '91 Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms. SIAM , Philadelphia, PA, pp. 344-350. ISBN 0-89791-376-0.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Many tree–structured computations are inherently parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. To maintain load balance, an on–line mapping algorithm must distribute processes equitably among processors. Additionally, the algorithm itself must be distributed in nature, and process allocation must be completed via message–passing with minimal communication overhead. This paper investigates bounds on the performance of deterministic and randomized algorithms for on–line tree embedding. In particular, we study tradeoffs between performance (load–balance) and communication overhead (message congest ion). We give a simple technique to derive lower bounds on the congestion that any on–line allocation algorithm must incur in order to guarantee load balance. This technique works for both randomized and deterministic algorithms, although we find that the performance of randomized on-line algorithms to be somewhat better than that of deterministic algorithms. Optimal bounds are achieved for several networks including multi–dimensional grids and butterflies.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:©1991 SIAM. The authors thank Jin-Yi Cai for helpful discussions. Sandeep Bhatt was supported at Caltech by DARPA Order Number 6202, monitored by ONR under contract N00014-87-K-0745. Sandeep Bhatt, David Greenberg and Pangfeng Liu were supported at Yale in part by Air Force grant AFOSR-89-0382, NSF grant CCR-88-07426, and NSF/DARPA grant CCR-89-08285. Tom Leighton was supported at MIT by Air Force grant AFOSR-89-0271, Army contract DAAL-03-86-K-0171, and DARPA contracts N0001489-J-1988 and N0001487-K-825.
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)6202
Office of Naval Research (ONR)N00014-87-K-0745
Air Force Office of Scientific Research (AFOSR)AFOSR-89-0382
Air Force Office of Scientific Research (AFOSR)AFOSR-89-0271
Army Research Office (ARO)DAAL-03-86-K-0171
Office of Naval Research (ONR)N0001489-J-1988
Office of Naval Research (ONR)N0001487-K-825
Record Number:CaltechAUTHORS:20160523-161347938
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67271
Deposited On:24 May 2016 00:31
Last Modified:03 Oct 2019 10:04

Repository Staff Only: item control page