Reference:

Tomáš Brázdil, Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Space-efficient scheduling of stochastically generated tasks. Technical report, arXiv.org, April 2010. Available at http://arxiv.org/abs/1004.4286.

Abstract:

We study the problem of scheduling tasks for execution by a processor when the tasks can stochastically generate new tasks. Tasks can be of different types, and each type has a fixed, known probability of generating other tasks. We present results on the random variable S^sigma modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler sigma. We obtain tail bounds for the distribution of S^sigma for both offline and online schedulers, and investigate the expected value of S^sigma.

Suggested BibTeX entry:

@techreport{BEKL10:ICALP-TR,
    author = {Tom\'{a}\v{s} Br\'{a}zdil and Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    institution = {arXiv.org},
    month = {April},
    note = {Available at http://arxiv.org/abs/1004.4286},
    title = {Space-Efficient Scheduling of Stochastically Generated Tasks},
    year = {2010}
}