An analysis of budgeted parallel search on conditional Galton-Watson trees

Understand

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.