Taking random walks to grow trees in hypercubes
Sandeep N. Bhatt, Jin‐Yi Cai · Journal of the ACM · 1993
Many parallel computationsare tree structured; as the computation proceeds, new processes are recursively created while others die out.Algorithms for maintaining dynamically evolving trees on fine-grain parallel architectures must have minimal overhead and must distribute processes evenly among processorsat run-time.A simple randomized strategy for maintaining dynamically evolving binary trees on hypercube networks is presented.The algorithm is distributed and does not require any global information.The algorithm guarantees that every pair of nodes adjacent in the tree are within distance O(loglog N)in an N-processor hypercube.Furthermore, if M is the number of active nodes in the tree at any instant, then, with ovenvhelming probability, no hypercube processors assigned more than 0(1 + (M\N))active nodes.The active nodes in a tree may constitute only leaves of the tree, or all nodes.As a corollary, with high probability, the load is evenly distributed throughout a computation whose running time is polynomial in N, the number of processors.The results can be generalized to bounded-degree trees.Our techniques justify the use of simple algorithms to efficiently parallelize any tree-based computation such as divide-andconquer, backtrack, functional expression evaluation, and to efficiently maintain dynamic data structures such as quad-trees that arise in scientific applications.A novel technique-tree surge~-is introduced to deal with dependencies inherent in trees.Together with tree surgery, the study of random walks is used to analyze the algorithm.