BRANCHING QUEUEING NETWORKS - THEIR INTRODUCTION AND NEAR-DECOMPOSABILITY ASYMPTOTICS/

A new class of models, which combines closed queueing networks with br anching processes, is introduced. The motivation comes from MIMD compu ters and other service systems in which the arrival of new work is alw ays triggered by the completion of former work, and the amount of arri ving work is variable. In the variant of branching/queueing networks s tudied here, a customer branches into a random and state-independent n umber of offspring upon completing its service. The process regenerate s whenever the population becomes extinct. Implications for less rudim entary variants are discussed. The ergodicity of the network and sever al other aspects are related to the expected total number of progeny o f an associated multitype Galton-Watson process. We give a formula for that expected number of progeny. The objects of main interest are the stationary state distribution and the throughputs. Closed-form soluti ons are available for the multi-server single-node model, and for homo geneous networks of infinite-servers. Generally, branching/queueing ne tworks do not seem to have a product-form state distribution. We propo se a conditional product-form approximation, and show that it is appro ached as a limit by branching/queueing networks with a slowly varying population size. The proof demonstrates an application of the nearly c omplete decomposability paradigm to an infinite state space.