Reference:

Tomáš Brázdil, Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Space-efficient scheduling of stochastically generated tasks. Information and Computation, 210:87–110, January 2012.

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:

@article{12BEKL:IC,
    author = {Tom\'{a}\v{s} Br\'{a}zdil and Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    journal = {Information and Computation},
    month = {January},
    pages = {87--110},
    title = {Space-Efficient Scheduling of Stochastically Generated Tasks},
    volume = {210},
    year = {2012}
}