The synchronization of Poisson processes and queueing networks with service and synchronization nodes

This paper investigates the dynamics of a synchronization node in isolation , and of networks of service and synchronization nodes. A synchronization n ode consists of M infinite capacity buffers, where tokens arriving on M dis tinct random input flows are stored (there is one buffer for each flow). To kens are held in the buffers until one is available from each flow. When th is occurs, a token is drawn from each buffer to form a group-token, which i s instantaneously released as a synchronized departure. Under independent P oisson inputs, the output of a synchronization node is shown to converge we akly (and in certain cases strongly) to a Poisson process with rate equal t o the minimum rate of the input flows. Hence synchronization preserves the Poisson property, as do superposition, Bernoulli sampling and M/M/1 queuein g operations. We then consider networks of synchronization and exponential server nodes with Bernoulli routeing and exogenous Poisson arrivals, extend ing the standard Jackson network model to include synchronization nodes. It is shown that if the synchronization skeleton of the network is acyclic (i .e. no token visits any synchronization node twice although it may visit a service node repeatedly), then the distribution of the joint queue-length p rocess of only the service nodes is product form (under standard stability conditions) and easily computable. Moreover, the network output flows conve rge weakly to Poisson processes. Finally, certain results for networks with finite capacity buffers are presented, and the limiting behavior of such n etworks as the buffer capacities become large is studied.