unni@sunset.sm.unisys.com (Unni Warrier) (08/27/87)
Distributed simulation has become of more than passing interest because of
the rapidly evolving multiprocessor technology. Chandy and Misra have
laid out the basics of the field in several publications. For those not
famaliar with the work, I refer you to Distributed Discrete-Event Simulation,
J. Misra, Computing Surveys, Vol 18, No 1, March 1986 , p 39-65.
(BTW, I saw a message in comp.os.research that was from a friend of Misra.
It said that since Bryant thought of the same ideas at the same time, Misra
would prefer the work to be referred to as "Chandy-Misra-Bryant").
In their work, they impose two conditions on "every physical system
imaginable". These are realizability and predictability.
Realizability says:
A message sent by a physical process at time t is a function of its initial
state, the time t, and the messages it has received up to and including t.
Predictability is more subtle:
Suppose the physical system has cycles, ie a set of processes pp(0), pp(1),
..pp(n-1) where pp(i) sends messages to pp(i+1) (mod n) and receives
messages from pp(i-1). Suppose that the message, if any, sent by pp(i)
at some time t depends on what pp(i) receives at time t for all i; then
we have a circular definition where the message received by every pp at time
t is a function of itself. In order to avoid such situations, we require
that for every cycle and t, there is a pp in the cycle and a real number
e (epsilon, actually, but my WYSE does not do Greek!), e > 0, such that
the messages sent by the pp along the cycle can be determined up to t + e
given the set of messages that the pp receives up to and including t.
Thus far, it has been Misra speaking, now here's my $0.02 worth:
Realizability says essentially, there shall be no "side-effects" on
a PP other than messages it receives from time 0, ie there is no
"action at a distance" that can affect the PP other than through
messages to it. ( It also imposes a strict ordering of dependencies in
the event list of the PP, that there be no "loops" in the time-ordering
of events. ). It also ALLOWS the output of the PP at time t to be
dependent on its input at time t.
Now, Predictability goes furthur, and says that it is also
possible to predict the future events (ie schedule some event in future
simulation time) with only knowledge of the present. Hence somehow
predictability is saying "you CANNOT have the PP's output dependent
on all the input upto time t, but only upto time t - e ( so OK, the
PP has to be in a cycle).
Compare the CAPitalized verbs in both paragraphs here.
I have the following two comments:
a. Are not predictability and realizability both prescriptions to
correlate input events with output events? And if they are, then
are they not the same animal by two different names?
b. If I am right, then isn't predictability the more restrictive
condition, and hence why do we need realizability at all?
unni@cam.unisys.com
*********************************************************************
Because there is some confusion about addressing among the group, the
following is appended. This will go away in 2 weeks.
All requests for inclusion in the mailing list should be sent to
..!sdcrdcf!sdcjove!modsim-request OR
"modsim-request@cam.unisys.com"
All articles for inclusion should be sent to
..!isdcrdcf!sdcjove!modsim OR
"modsim@cam.unisys.com"
Any private correspondence regarding the list should be sent to me at
..!sdcrdcf!sdcjove!unni OR
"unni@cam.unisys.com"
Ma Bell (may she rest in peace!): (213) 829-7511 X 5694
US mail: Unni Warrier, Unisys, MS 41-02,
2400 Colorado Ave, Santa Monica CA 90406