id: 06070929
dt: a
an: 06070929
au: Brázdil, Tomáš; Kiefer, Stefan
ti: Stabilization of branching queueing networks.
so: Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on
    theoretical aspects of computer science, Paris, France, February 29th
    ‒ March 3rd, 2012. Wadern: Schloss Dagstuhl ‒ Leibniz Zentrum für
    Informatik (ISBN 978-3-939897-35-4). LIPICS ‒ Leibniz International
    Proceedings in Informatics 14, 507-518, electronic only (2012).
py: 2012
pu: Wadern: Schloss Dagstuhl ‒ Leibniz Zentrum für Informatik
la: EN
cc: 
ut: continuous-time Markov decision processes; infinite-state systems;
    performance analysis
ci: 
li: doi:10.4230/LIPIcs.STACS.2012.507
ab: Summary: Queueing networks are gaining attraction for the performance
    analysis of parallel computer systems. A Jackson network is a set of
    interconnected servers, where the completion of a job at server $i$ may
    result in the creation of a new job for server $j$. We propose to
    extend Jackson networks by“branching" and by “control" features.
    Both extensions are new and substantially expand the modelling power of
    Jackson networks. On the other hand, the extensions raise computational
    questions, particularly concerning the stability of the networks, i.e,
    the ergodicity of the underlying Markov chain. We show for our extended
    model that it is decidable in polynomial time if there exists a
    controller that achieves stability. Moreover, if such a controller
    exists, one can efficiently compute a static randomized controller
    which stabilizes the network in a very strong sense; in particular, all
    moments of the queue sizes are finite.
rv: