Space-efficient scheduling of stochastically generated tasks
| Authors | |
|---|---|
| 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 | |
| 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: |