Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Space-Efficient Scheduling of Stochastically Generated Tasks

Reference:

Tomáš Brázdil, Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Space-efficient scheduling of stochastically generated tasks. Information and Computation, 210:87–110, 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 modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler . We obtain tail bounds for the distribution of for both offline and online schedulers, and investigate its expected value.

Suggested BibTeX entry:

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

PDF (193 kB)
Tech report version, Conference version