  Recently Avis and Jordan have demonstrated the efficiency of a simple
technique called budgeting for the parallelization of a number of tree search
algorithms. The idea is to limit the amount of work that a processor performs
before it terminates its search and returns any unexplored nodes to a master
process. This limit is set by a critical budget parameter which determines the
overhead of the process. In this paper we study the behaviour of the budget
parameter on conditional Galton-Watson trees obtaining asymptotically tight
bounds on this overhead. We present empirical results to show that this bound
is surprisingly accurate in practice.

Data Structures and Algorithms;Distributed, Parallel, and Cluster Computing