Space-efficient scheduling of stochastically generated tasks

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BRÁZDIL Tomáš ESPARZA Javier KIEFER Stefan LUTTENBERGER Michael

Year of publication 2010
Type Article in Proceedings
Conference Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP 2010)
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-642-14162-1_45
Field Informatics
Keywords infinite-state stochastic models; process creation; probabilistic verification
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.