Reference:

Tomáš Brázdil, Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Space-efficient scheduling of stochastically generated tasks. In Samson Abramsky et al., editor, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), part II, volume 6199 of LNCS, ARCoSS, pages 539–550, Bordeaux, France, 2010. Springer.

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:

@inproceedings{BEKL10:ICALP,
    address = {Bordeaux, France},
    author = {Tom\'{a}\v{s} Br\'{a}zdil and Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    booktitle = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), part II},
    editor = {Samson Abramsky et al.},
    pages = {539--550},
    publisher = {Springer},
    series = {LNCS, ARCoSS},
    title = {Space-Efficient Scheduling of Stochastically Generated Tasks},
    volume = {6199},
    year = {2010}
}