Report Number: CS-TR-98-1613
Institution: Stanford University, Department of Computer Science
Title: On the synchronization of Poisson processes and queueing
networks with service and synchronization nodes.
Author: Prabhakar, Balaji
Author: Bambos, Nicholas
Author: Mountford, Tom
Date: October 1998
Abstract: This paper investigates the dynamics of a synchronization
node in isolation, and of networks of service and
synchronization nodes. A synchronization node consists of $M$
infinite capacity buffers, where tokens arriving on $M$
distinct random input flows are stored (there is one buffer
for each flow). Tokens are held in the buffers until one is
available from each flow. When this occurs, a token is drawn
from each buffer to form a group-token, which is
instantaneously released as a synchronized departure.
Under independent Poisson inputs, the output of a
synchronization node is shown to converge weakly (and in
certain cases strongly) to a Poisson process with rate equal
to the minimum rate of the input flows. Hence synchronization
preserves the Poisson property, as do superposition,
Bernoulli sampling and M/M/1 queueing operations.
We then consider networks of synchronization and exponential
server nodes with Bernoulli routing and exogenous Poisson
arrivals, extending 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 process of only the service nodes is
product form (under standard stability conditions) and easily
computable. Moreover, the network output flows converge
weakly to Poisson processes.
Finally, certain results for networks with finite capacity
buffers are presented, and the limiting behavior of such
networks as the buffer capacities become large is studied.