On the stability condition of a precedence-based queueing discipline

The queueing model known as precedence-based queueing discipline, proposed in [8] by Tsitsiklis et al. is addressed. In this queueing model, there are infinitely many servers and for any pair of customers i and j such that i arrived later than j, there is a fixed probability p that i will have to wait for the end of the execution of j before starting its execution. In the case where the customer service times are deterministic and the arrival process is Poisson, these authors have derived the stability condition which determines the maximum arrival rate that keeps the system stable. For more general statistics, they conjectured that the stability condition would possibly depend on the complete service time distribution functions but only on the first moment of the inter-arrival times. In this paper, we consider this queueing model and relax the restrictive statistical assumptions mentioned above by only assuming that the service times and the inter-arrival times are stationary and ergodic sequences, so that these variables can receive general distribution functions and be correlated. We derive a general expression for the stability condition which in turn proves the above conjectures. The results are obtained by establishing pathwise evolution equations for these queueing systems, and then a schema which, in certain sense, generalizes the schema of Loynes for the G/G/1 queues.