COMPACT MODELS OF RANDOM POLLING SYSTEMS - Modelling with Generalised Stochastic Petri Nets - page 218

mediate transitions, with t a , t q , and t r . Two P-semiflows cover all the
GSPN places. The first P-semiflow covers places p a , p q , and p s , and the
resulting P-invariant is M(p a ) + M(p q ) + M(p s ) = N. The second P-
semiflow covers places p p , p s , p w and p r . The resulting P-invariant is
M(p p ) + M(p s ) + M(p w ) + M(p r ) = S. As a result, the GSPN model
is bounded. Three T-semiflows cover all transitions, and the GSPN model
is live, and reversible. The first two T-semiflows correspond to a walk that
is not followed by a service: they cover T w and either t a or t s . The third
T-semiflow corresponds to a walk followed by a service: it covers T w , t q , t,
T s , and T a .

9.4.2 Walking before choosing!

The abstract GSPN model presented in Fig. 9.7, like the GSPN model pre-
viously shown in Fig. 9.6, is such that servers first walk, and then decide
which queue to visit next. Remember that this is just a simplification that
we introduced in the model: in the real system, servers first randomly select
the next queue to be visited and then walk towards it; the inversion of the
two actions in the model is one of the results obtained by the exploitation
of the symmetry in the model abstraction process.
There is an important difference in the inversion of walks and choices in the
two models. Indeed, while for the GSPN model in Fig. 9.6 the inversion is
optional, and was introduced only because it allows a reduction in the state
space size (and because it permits the GSPN model in Fig. 9.7 to be more
easily explained), for the GSPN model in Fig. 9.7 the inversion is mandatory.
This necessity stems from the fact that choices are modelled probabilistically,
using information derived from the state of the system when servers visit the
queues, and thus exactly when the decision is taken in the real system (the
probabilities associated with immediate transitions t a ,t q and t s depend on
the number of tokens in p a ,p q and p s ). If the choices were made before the
walk using the same probabilistic mechanism, it could happen that when the
server reaches the chosen queue after the walk, the state of the system (and in
particular the state of the chosen queue) has changed (because some other
transition may have fired while the transition representing the walk was
working), so that the choice would have been based on incorrect probability
values.
To understand this incorrect behaviour, consider for example the case in
which only one queue contains a waiting customer (only one token is in place
p q ). Assume that a server chooses that queue (with probability 1/N), and
then starts walking towards it. Before the walk terminates, another server
chooses the same queue (again with probability 1/N) and starts walking.
When the first walk ends, the service at the chosen queue begins, and no
waiting customer remains in the system. Thus, at the end of the walk of
the second server, no waiting customer will be found at the selected queue.