Masaryk University, Czech Republic
4pm Tuesday, 24th November, 2009
Room 4.31/33, Informatics Forum
In this talk I will present results on 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 are interested in the random variables modeling the time and space needed to completely execute a task T, that is, to empty the pool of unprocessed tasks assuming that initially the pool only contains the task T. We derive tail bounds for the distributions of these variables for various classes of schedulers. We also provide bounds on the expected values of these variables.
This talk is based on a joint work with Javier Esparza, Stefan Kiefer and Michael Luttenberger.