Scheduling of Stochastically Generated Tasks

Date: Thursday, November 24, 2011
Speaker: Tomas Brazdil
Venue: IST Austria

In this talk I will present results on the problem of scheduling tasksfor execution by a processor when the tasks can stochasticallygenerate new tasks. Tasks can be of different types, and each type hasa fixed, known probability of generating d tasks for each number d. Weare interested in the random variables modeling the time and spaceneeded to completely execute a task T, that is, to empty the pool ofunprocessed tasks assuming that initially the pool only contains thetask T. We derive tail bounds for the distributions of these variablesfor various classes of schedulers. We also provide bounds on theexpected values of these variables.

Posted in RiSE Seminar