Insensitivity in discrete-time generalized semi-Markov processes allowing multiple events and probabilistic service scheduling (Q1894617)

The reemergence of discrete time models in queueing theory due to necessities in modern telecommunication networks focused interest on the structural behaviour of such systems. In the continuous time setting the most successful approach to a structure theory of general queueing system was to embed these special systems into the class of generalized semi- Markov schemes and generalized semi-Markov processes. The paper mimics the development there in the case of discrete time systems, e.g., networks of queues. While the general idea is analogous to the continuous time setting, the technical difficulties are much harder -- due to the occurrence of simultaneous events, which means: At the same time instant several interarrival and/or service times may expire. Handling these simultaneous events poses the difficulties but on the other hand is one of the main features of discrete time systems. Considering the service and interarrival times as ``life times'' of state components, the insensitivity problem is: Under which conditions on the system's structure does the steady state distribution of the state process (which does not include the life times) depend on the life time distribution only through their means? The authors provide balance conditions for insensitivity to hold, which are stated in terms of the state process' equilibrium distribution and the transition laws concerning the development of the physical state process. These are equivalent to obtaining product form steady-states, i.e., the equilibrium probabilities of the supplemented state process (including residual life time components) factor into a term concerning the physical state and terms concerning the residual life times. For the case of systems with such a product form equilibrium the state distribution can be computed by a recursive algorithm. Some special cases are discussed in detail, which lead to less involved formulas, mostly depending on a reduction of the system's complexity by introducing rules which guarantee a more homogeneous transition behaviour.