Reference:

Tomáš Brázdil, Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Space-efficient scheduling of stochastically generated tasks. Technical report, Technische Universität München, Institut für Informatik, April 2009.

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 d tasks for each number d. 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 also bounds on the expected value of S^sigma.

Suggested BibTeX entry:

@techreport{BEKL09:techRep,
    author = {Tom\'{a}\v{s} Br\'{a}zdil and Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    institution = {Technische Universit\"{a}t M\"{u}nchen, Institut f\"{u}r Informatik},
    month = {April},
    title = {Space-Efficient Scheduling of Stochastically Generated Tasks},
    year = {2009}
}