Space-Efficient Scheduling of Stochastically Generated Tasks

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 expectation of S^sigma.