Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!rochester!rutgers!ames!sdcsvax!darrell
From: unni@sunset.sm.unisys.com (Unni Warrier)
Newsgroups: comp.os.research
Subject: Distributed simulation paradigms.
Message-ID: <3557@sdcsvax.UCSD.EDU>
Date: Thu, 30-Jul-87 18:39:28 EDT
Article-I.D.: sdcsvax.3557
Posted: Thu Jul 30 18:39:28 1987
Date-Received: Sat, 1-Aug-87 15:51:08 EDT
Sender: darrell@sdcsvax.UCSD.EDU
Lines: 31
Approved: mod-os@sdcsvax.uucp

Two of the more famous paradigms for distributed simulation are the
Chandy-Misra scheme (CM) and the Jefferson time warp scheme (TW).  CM allows
the distributed simulation to proceed till a deadlock and then have ways of
detecting the deadlock, and resolving it.  A deadlock arises when each of the
processes in a cycle is waiting for a message from the previous process.  TW
allows the simulation to proceed and has a rollback mechanism for dealing
with out-of-order timestamped messages.  Hence one question is:  has anyone
used TW or CM in their distributed simulations? What are your experiences?

How do the two schemes compare in performance?  One way to answer the
question is to model the two methods.  The problem is that I have not come
across any models that can give a general answer to these questions.  Some
tradeoffs can be identified, in a general sense.  For example, if processing
power were free, the cost of rollback would be free, and hence TW may win.
However, if communications bandwidth were free, then extra messages would not
cost us anything, so having a large number of null messages (like in one of
the CM schemes) would be free.  Hence it is possible that CM may win.  But,
on the other hand, there is no guarantee that the number of messages in TW
are less than those in CM, specially in the face of significant rollbacks
precolating throough the network. Thus the problem with this sort of sweeping
generalization is that the specifics of a simulation may actually favour the
contra-indicated method.  Perhaps someone out there has taken a more
structured look at these problems and actually has some answers.  I would be
interested in knowing what these models are and what the answers are.

For those unfamaliar with the field, here is a reference:

Distributed Discrete-Event Simulation, J. Misra, Computing Surveys, Vol 18,
No 1, March 1986, p 39-65.

unni@cam.unisys.com