Take a walk, grow a tree
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 469-478
- https://doi.org/10.1109/sfcs.1988.21963
Abstract
A simple randomized algorithm is presented for maintaining dynamically evolving binary trees on hypercube networks. The algorithm guarantees that: (1) nodes adjacent in the tree are within distance O(log log N) in an N-processor hypercube, and (2) with overwhelming probability, no hypercube processor is assigned more than O(1+M/N) tree nodes, where M is the number of nodes in the tree. The algorithm is distributed and does not require any global information. This is the first load-balancing algorithm with provably good performance. The algorithm can be used to parallelize efficiently any tree-based computation. It can also be used to maintain efficiently dynamic data structures such as quadtrees. A technique called tree surgery is introduced to deal with dependencies inherent in trees. Together with tree surgery, the study of random walks is used to analyze the algorithm.Keywords
This publication has 4 references indexed in Scilit:
- A randomized parallel branch-and-bound procedurePublished by Association for Computing Machinery (ACM) ,1988
- Optimal simulations of tree machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Adaptive load sharing in homogeneous distributed systemsIEEE Transactions on Software Engineering, 1986
- Minimization Algorithms and Random Walk on the $d$-CubeThe Annals of Probability, 1983