# Parallel Simulation of Continuous Time Markov Chains Using Uniformization with Adaptive Rates

Original Publication Date: 1993-Jul-01

Included in the Prior Art Database: 2005-Mar-19

## Publishing Venue

IBM

## Related People

Heidelberger, P: AUTHOR [+2]

## Abstract

An algorithm, based on uniformization with adaptively controlled rates, for simulating certain Continuous Time Markov Chains on parallel processors is described.

**This text was extracted from an ASCII text file.**

**This is the abbreviated version, containing approximately 37% of the total text.**

Parallel Simulation of Continuous Time Markov Chains Using Uniformization with Adaptive Rates

An algorithm,
based on uniformization with adaptively

controlled rates, for simulating certain Continuous Time Markov

Chains on parallel processors is described.

Discrete
event simulations can be computationally expensive.

Therefore, researchers have looked to parallel processing techniques

to speed up such simulations. There are
currently two general

approaches to parallel simulation:
optimistic and conservative. See

[1] for a more complete discussion and a
thorough bibliography.

Both optimistic and conservative approaches for parallel simulation

of certain Continuous Time Markov Chains (CTMCs) have been described

in [2,3,4,5]. These techniques are based
on uniformization.

Uniformization allows processors to easily agree upon exactly what

times they need to exchange messages. In
the above algorithms, the

maximum possible rate of external events from processor i to

processor j, lambda (i,j), is identified for each pair of processors.

Poisson Processes, lbrace N(i,j, t) , t ge 0 rbrace with rates

lambda(i,j) are generated. The times in
these Poisson Processes are

used as synchronization points in the simulation.

Let
lambda(i,j,t) denote the actual (state-dependent) rate of

external i to j transitions at time t.
Suppose T is a random time

sampled from the Poisson Process lbrace N(i,j, t) rbrace. Then T is

a real transition in the CTMC with probability lambda(i,j,T)/ lambda

(i,j) , and it is a "pseudo event"
with probability 1 -

lambda(i,j,T)/ lambda (i,j).

Parallel
simulations performed in this manner are efficient if

most events are internal (i.e., do not require communication between

two processors), and if there are not an excessive number of external

pseudo events resulting in an unnecessarily large number of

synchronizations. If lambda(i,j,t) /
lambda (i,j) ltlt 1 , for most

values of t, then the simulation may be inefficient. Since

lambda(i,j) corresponds to the maximum possible rate of transitions

from i to j, it may be much larger than the typical rate of

transitions from i to j. For example, in
a queueing network, suppose

there are N queues assigned to processor i such that whenever a job

leaves one of these queues it goes to a queue assigned to processor

j. Suppose the service times on each of
these N queues have a common

hyperexponential distribution with rates r(1) and r(2). Then

lambda(i,j)= N times 'max'( r(1),r(2)) which is obtained by assuming

that each queue is busy in the fastest phase.
However the transition

rate at time t is given by lambda (i,j,t) = N(1,t) times r(1) +

N(2,t) times r(2) where N(1,t) is the number of queues busy at rate

r(1) and N(2,t) is the number of queues busy at rate r(2). If r(2)

gtgt r(1) but 'E' lbracket N(2,t) rbracket ltlt N, then, with high

probability, lambda(i,j,t) / lambda (i,j) ltlt 1.

In this note, it is shown ho...