2010
Space-efficient scheduling of stochastically generated tasks
BRÁZDIL, Tomáš; Javier ESPARZA; Stefan KIEFER a Michael LUTTENBERGERZákladní údaje
Originální název
Space-efficient scheduling of stochastically generated tasks
Autoři
BRÁZDIL, Tomáš; Javier ESPARZA; Stefan KIEFER a Michael LUTTENBERGER
Vydání
Berlin, Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), od s. 539–550, 12 s. 2010
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14330/10:00065891
Organizační jednotka
Fakulta informatiky
ISBN
978-3-642-14161-4
ISSN
UT WoS
Klíčová slova anglicky
infinite-state stochastic models; process creation; probabilistic verification
Příznaky
Mezinárodní význam
Změněno: 30. 4. 2014 05:25, RNDr. Pavel Šmerk, Ph.D.
V originále
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.
Česky
V článku studujeme problém plánování stochasticky generovaných úloh. Úlohy mohou být různého typu přičemž každý typ má fixní pravděpodobnost generování dalších úloh. V článku prezentujeme výsledky týkající se náhodné proměnné S^sigma, která modeluje maximální prostor, který procesor potřebuje k uložení aktivních úloh v závislosti na plánovači sigma. Prezentujeme odhady na distribuci proměnné S^sigma pro offline a online plánovače a studujeme očekávanou hodnotu proměnné S^sigma. 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.
Návaznosti
| GAP202/10/1469, projekt VaV |
| ||
| 1M0545, projekt VaV |
|