Abstract
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 \(\mathbb{E}{S^{\sigma}}\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, K., Leiserson, C.E., He, Y., Hsu, W.J.: Adaptive work-stealing with parallelism feedback. ACM TOCS 26(3) (2008)
Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed microprocessors. Theory of Computing Systems 34, 115–144 (2001)
Athreya, K.B.: On the maximum sequence of a critical branching process. Annals of Probability 16, 502–507 (1988)
Athreya, K.B., Ney, P.E.: Branching Processes. Springer, Heidelberg (1972)
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, Heidelberg (1998)
Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. Journal of the ACM 46(5), 720–748 (1999)
Borovkov, K.A., Vatutin, V.A.: On distribution tails and expectations of maxima in critical branching processes. Journal of Applied Probability 33(3), 614–622 (1996)
Brázdil, T., Esparza, J., Kiefer, S.: On the memory consumption of probabilistic pushdown automata. In: Proceedings of FSTTCS, pp. 49–60 (2009)
Brázdil, T., Esparza, J., Kiefer, S., Luttenberger, M.: Space-efficient scheduling of stochastically generated tasks. Technical report (2010), http://arxiv.org/abs/1004.4286
Esparza, J., Kiefer, S., Luttenberger, M.: An extension of Newton’s method to ω-continuous semirings. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 157–168. Springer, Heidelberg (2007)
Esparza, J., Kiefer, S., Luttenberger, M.: On fixed point equations over commutative semirings. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 296–307. Springer, Heidelberg (2007)
Esparza, J., Kiefer, S., Luttenberger, M.: Convergence thresholds of Newton’s method for monotone polynomial equations. In: STACS 2008, pp. 289–300 (2008)
Esparza, J., Kučera, A., Mayr, R.: Quantitative analysis of probabilistic pushdown automata: Expectations and variances. In: LICS 2005, pp. 117–126. IEEE, Los Alamitos (2005)
Esparza, J., Kučera, A., Mayr, R.: Model checking probabilistic pushdown automata. In: LICS 2004, pp. 12–21. IEEE Computer Society Press, Los Alamitos (2004)
Etessami, K., Yannakakis, M.: Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations. Journal of the ACM 56(1), 1–66 (2009)
Feller, W.: An introduction to probability theory and its applications, vol. I. John Wiley & Sons, Chichester (1968)
Harris, T.E.: The Theory of Branching Processes. Springer, Heidelberg (1963)
Karp, R.M., Zhang, Y.: Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM 40(3), 765–789 (1993)
Kiefer, S., Luttenberger, M., Esparza, J.: On the convergence of Newton’s method for monotone systems of polynomial equations. In: STOC 2007, pp. 217–226. ACM, New York (2007)
Lindvall, T.: On the maximum of a branching process. Scandinavian Journal of Statistics 3, 209–214 (1976)
Narlikar, G.J., Belloch, G.E.: Space-efficient scheduling of nested parallelism. ACM TOPLAS 21(1), 138–173 (1999)
Nerman, O.: On the maximal generation size of a non-critical galton-watson process. Scandinavian Journal of Statistics 4(3), 131–135 (1977)
Ortega, J.M., Rheinboldt, W.C.: Iterative solution of nonlinear equations in several variables. Academic Press, London (1970)
Pakes, A.G.: A limit theorem for the maxima of the para-critical simple branching process. Advances in Applied Probability 30, 740–756 (1998)
Spitzer, F.: Principles of Random Walk. Springer, Heidelberg (1976)
Spătaru, A.: A maximum sequence in a critical multitype branching process. Journal of Applied Probability 28(4), 893–897 (1991)
Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brázdil, T., Esparza, J., Kiefer, S., Luttenberger, M. (2010). Space-Efficient Scheduling of Stochastically Generated Tasks. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds) Automata, Languages and Programming. ICALP 2010. Lecture Notes in Computer Science, vol 6199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14162-1_45
Download citation
DOI: https://doi.org/10.1007/978-3-642-14162-1_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14161-4
Online ISBN: 978-3-642-14162-1
eBook Packages: Computer ScienceComputer Science (R0)