TY - GEN
T1 - Space-efficient scheduling of stochastically generated tasks
AU - Brázdil, Tomáš
AU - Esparza, Javier
AU - Kiefer, Stefan
AU - Luttenberger, Michael
N1 - Funding Information:
✩ A preliminary version of this work appeared at the 37th International Colloquium on Automata, Languages and Programming, ICALP 2010. * Corresponding author. E-mail addresses: [email protected] (T. Brázdil), [email protected] (J. Esparza), [email protected] (S. Kiefer), [email protected] (M. Luttenberger). 1 Supported by Czech Science Foundation, grant No. P202/10/1469. 2 Supported by the EPSRC project Automated Verification of Probabilistic Programs and by a postdoctoral fellowship of the German Academic Exchange Service (DAAD).
PY - 2010
Y1 - 2010
N2 - 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 σ modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler σ. We obtain tail bounds for the distribution of S σ for both offline and online schedulers, and investigate the expected value .
AB - 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 σ modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler σ. We obtain tail bounds for the distribution of S σ for both offline and online schedulers, and investigate the expected value .
UR - http://www.scopus.com/inward/record.url?scp=77955323687&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-14162-1_45
DO - 10.1007/978-3-642-14162-1_45
M3 - Conference contribution
AN - SCOPUS:77955323687
SN - 3642141617
SN - 9783642141614
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 539
EP - 550
BT - Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010
Y2 - 6 July 2010 through 10 July 2010
ER -