University of California, Berkeley
Duncan Temple Lang
University of California, Davis
Parallel computing allows us to break up our programs into smaller pieces that can run simultaneously on different CPUs. Sometimes a program spawns another program/job that needs to wait before it can begin its work because it requires the results of another program that has not completed. In this situation even where there are ‘infinitely’ many CPUs available, a queue of interdependent tasks will form. Tsitsiklis, Papadimitriou, and Humblet  studied the behavior of systems of interdependent jobs. One of the questions that interested them was: what is the distribution of the ...