ken@gvax.cs.cornell.edu (Ken Birman) (05/19/89)
In article <5512@hubcap.clemson.edu> landman@Sun.COM (Howard A. Landman) writes: >..... We are running massive gate-level simulations using >simulator S on Sun workstations. We have two problems. (1) Our largest >examples won't fit in 128 MB (maximum memory for the machines). (2) The >simulation takes too long...... Is Linda a reasonable basis on which to >build this system? While Linda probably IS a reasonable basis on which to build this system, I want to suggest an alternative. In brousing this group, I saw quite a discussion concerning parallel make, and would like to comment on this too. My group has developed a distributed computing technology called "ISIS" that can be used to solve these kinds of problems, too. We believe that ISIS has some important advantages over Linda in certain situations and for certain architectures. (We are also convinced that Linda has advantages over ISIS in some situations/architectures). ISIS focuses on supporting replication and mechanisms for subdivision of tasks in loosely coupled environments. Unlike Linda, ISIS provides fault-tolerance and a way to code algorithms in which a set of processes explicitly coordinate their behavior, in a synchronized way, but without requiring a substantial exchange of data. Our system is presented as a toolkit -- a set of subroutines that appear to extend the kernel. It can currently be used from C, Fortran and Common LISP on quite a range of UNIX and MACH machines, and has been picked up by about 200 sites worldwide (source too). We have quite a bit of information on ISIS, including a blurb that I appended to this at the end. I won't repeat the usual information here. Instead, let me comment on when I think that our approach might dominate Linda -- and when I think that Linda might be the approach of choice. Offhand, I don't actually know of a 3rd approach that fits this general framework, unless one includes Jefferson's time-warp work (you simulation users will want to find out about that, too!) Linda seems to be quite a powerful approach if: the problem decomposes nicely into data structures that can be shared in the tuple-space and won't need to be accessed often. My strong personal feeling is that few programmers would be able to use Linda for work involving complex data structures, complex synchronization requirements, or fault-tolerance, and that the approach is ill-suited to applications that run for long periods of time while reconfiguring dynamically. I've written on this subject; people interested might want to request a preprint of a chapter in a textbook that will be out next summer ("An advanced course on distributed computing from Adison Wesley; Sape Mullender ed.) As for ISIS, I think the system is well suited to network computations that may be long-running, highly dynamic/reconfigurable, fault-tolerant, etc. On the other hand, if an application is just ideal for Linda, you will probably find that the ISIS approach is cumbersome by comparison. In the limit, if Linda had replication it would probably look almost exactly like what ISIS would look like if it provided a "Linda tool". Perhaps a good research topic for someone... Also, because ISIS is oriented towards fault-tolerance and replication, our system has a higher overhead than some of the recent versions of Linda, which basically do all tuple operations by a single RPC. What ISIS is especially good at is getting a set of processes to behave in a coordinated way without interacting a great deal for purposes of coordination. The system is quite sophisticated about this. As an example, you can arrange an aplication to subdivide the work involved in performing a task n ways, where n is variable. Thus, if the request were to look up the name associated with a known phone number in a dynamically changing telephone directory, with a variable number of "looker-upper" processes in the system, ISIS provides a rather simple way to actually devise a solution that correctly subdivides the task (dynamically), searching each "page" exactly once. In a system like Linda my guess is that this would be hard. Probably you would need a tuple for each page, or set of pages, and perhaps a second kind of tuple to describe pages that changed while you were already searching. Moreover, you can make the ISIS version fault-tolerant. So far, this would be hard to do in Linda, although the Yale people have told me about some really neat current work on making Linda fault-tolerant. My deep sense of this is that ISIS and Linda are gradually converging. Both represent technologies that get a lot of milage out of a certain style of programming, although the interfaces are quite different and the systems are engineered differently. ISIS used to be very sluggish, but this is less true recently. By now, if you have a faster way to multicast than us, you can plug your scheme into ISIS and we'll use it most of the time. And, our own "fast scheme" is about 50 times faster than the first version of ISIS that we instrumented... we now can beat SUN at RPC on the same machines and with the same types of data, for example, although not by much. One issue relevant to this newsgroup is that ISIS is not currently running on any real parallel machines. However, we are thinking seriously about how such a version of ISIS could be built, and I think this is a likely research direction for my group. I think the execution model we use (virtual synchrony) is quite elegant and powerful, and that although the current implementation might have to be redone for such a machine, this model could be of great value in developing parallel software for the same reason that it lets us solve problems like the one outlined above. The remainder of this posting contains a blurb on ISIS. Many of you will have seen this elsewhere. It hasn't changed recently... Ken Birman PS: You might want to subscribe to comp.sys.isis if you are considering using ISIS. --- isis.blurb follows --- This is to announce the availability of a public distribution of the ISIS System, a toolkit for distributed and fault-tolerant programming. The initial version of ISIS runs on UNIX on SUN, DEC, GOULD, and HP systems, although ports to other UNIX-like systems are planned for the future. No kernel changes are needed to support ISIS; you just roll it in and should be able to use it immediately. The current implementation of ISIS performs well in networks of up to about 100-200 sites. --- Who might find ISIS useful? --- You will find ISIS useful if you are interested in developing relatively sophisticated distributed programs under UNIX (eventu- ally, other systems too). These include programs that distribute computations over multiple processes, need fault-tolerance, coor- dinate activities underway at several places in a network, recover automatically from software and hardware crashes, and/or dynamically reconfigure while maintaining some sort of distri- buted correctness constraint at all times. ISIS is also useful in building certain types of distributed real time systems. Here are examples of problems to which ISIS has been applied: o On the factory floor, we are working with an industrial research group that is using ISIS to program decentralized cell controllers. They need to arrive at a modular, expand- able, fault-tolerant distributed system. ISIS makes it pos- sible for them to build such a system without a huge invest- ment of effort. (The ISIS group also working closely with an automation standards consortium called ANSA, headed by Andrew Herbert in Cambridge). o As part of a network file system, we built an interface to the UNIX NFS (we call ours the "RNFS") that supports tran- sparent file replication and fault-tolerance. The RNFS speaks NFS protocols but employs ISIS internally to maintain a consistent distributed state. For most operations, the RNFS performance is at worst 50-75% of that of a normal NFS -- despite supporting file replication and fault-tolerance. o A parallel "make" program. Here, ISIS was used within a control program that splits up large software recompilation tasks and runs them on idle workstations, tolerating failures and dynamically adapting if a workstation is reclaimed by its owner. o In a hospital, we have looked at using ISIS to manage repli- cated data and to coordinate activities that may span multi- ple machines. The problem here is the need for absolute correctness: if a doctor is to trust a network to carry out orders that might impact on patient health, there is no room for errors due to race conditions or failures. At the same time, cost considerations argue for distributed systems that can be expanded slowly in a fully decentralized manner. ISIS addresses both of these issues: it makes it far easier to build a reliable, correct, distributed system that will manage replicated data and provide complex distributed behaviors. And, ISIS is designed to scale well. o For programming numerical algorithms. One group at Cornell used ISIS to distribute matrix computations over large numbers of workstations. They did this because the worksta- tions were available, mostly idle, and added up to a tremen- dous computational engine. o In a particle physics experiment. We are talking to one group that hopes to use ISIS to implement a distributed con- trol program. It will operate data collection devices, farm out the particle track calculations onto lightly loaded workstations, collect the results, and adapt to failures automatically by reconfiguring and shifting any interrupted computation to an operational machine. The problems above are characterized by several features. First, they would all be very difficult to solve using remote procedure calls or transactions against some shared database. They have complex, distributed correctness constraints on them: what hap- pens at site "a" often requires a coordinated action at site "b" to be correct. And, they do a lot of work in the application program itself, so that the ISIS communication mechanism is not the bottleneck. If you have an application like this, or are interested in taking on this kind of application, ISIS may be a big win for you. Instead of investing resources in building an environment within which to solve your application, using ISIS means that you can tackle the application immediately, and get something working much faster than if you start with RPC (remote procedure calls). --- What ISIS does --- The ISIS system has been under development for several years at Cornell University. After an initial focus on transactional "resilient objects", the emphasis shifted in 1986 to a toolkit style of programming. This approach stresses distributed con- sistency in applications that manage replicated data or that require distributed actions to be taken in response to events occurring in the system. An "event" could be a user request on a distributed service, a change to the system configuration result- ing from a process or site failure or recovery, a timeout, etc. The ISIS toolkit uses a subroutine call style interface similar to the interface to any conventional operating system. The pri- mary difference, however, is that ISIS functions as a meta- operating system. ISIS system calls result in actions that may span multiple processes and machines in the network. Moreover, ISIS provides a novel "virtual consistency" property to its users. This property makes it easy to build software in which currently executing processes behave in a coordinated way, main- tain replicated data, or otherwise satisfy a system-wide correct- ness property. Moreover, virtual synchrony makes even complex operations look atomic, which generally implies that toolkit functions will not interfere with one another. One can take advantage of this to develop distributed ISIS software in a sim- ple step-by-step style, starting with a non-distributed program, then adding replicated data or backup processes for fault- tolerance or higher availability, then extending the distributed solution to support dynamic reconfiguration, etc. ISIS provides a really unique style of distributed programming -- at least if your distributed computing problems run up against the issues we address. For such applications, the ISIS programming style is both easy and intuitive. ISIS is really intended for, and is good at, problems that draw heavily on replication of data and coordination of actions by a set of processes that know about one another's existence. For example, in a factory, one might need to coordinate the actions of a set of machine-controlled drills at a manufacturing cell. Each drill would do its part of the overall work to be done, using a coordinated scheduling policy that avoids collisions between the drill heads, and with fault-tolerance mechanisms to deal with bits breaking. ISIS is ideally suited to solving prob- lems like this one. Similar problems arise in any distributed setting, be it local-area network software for the office or a CAD problem, or the automation of a critical care system in a hospital. ISIS is not intended for transactional database applications. If this is what you need, you should obtain one of the many such systems that are now available. On the other hand, ISIS would be useful if your goal is to build a front-end in a setting that needs databases. The point is that most database systems are designed to avoid interference between simultaneously executing processes. If your application also needs cooperation between processes doing things concurrently at several places, you may find this aspect hard to solve using just a database because databases force the interactions to be done indirectly through the shared data. ISIS is good for solving this kind of problem, because it provides a direct way to replicate control informa- tion, coordinate the actions of the front-end processes, and to detect and react to failures. ISIS itself runs as a user-domain program on UNIX systems sup- porting the TCP/IP protocol suite. It currently is operational on SUN, DEC, GOULD and HP versions of UNIX. A MACH version is now running at Cornell and will be released later this spring, as will a FORTRAN-ISIS interface and a port to the APOLLO UNIX. And, a LISP-ISIS interface (from Allegro) is now being tested and will be included into ISIS release V1.2 (planned for May 1989). The actual set of tools includes the following: o High performance mechanisms supporting lightweight tasks in UNIX, a simple message-passing facility, and a very simple and uniform addressing mechanism. Users do not work directly with things like ports, sockets, binding, connect- ing, etc. ISIS handles all of this. o A process "grouping" facility, which permits processes to dynamically form and leave symbolically-named associations. The system serializes changes to the membership of each group: all members see the same sequence of changes. Groups names can be used as a location-transparent address. o A suite of broadcast protocols integrated with a group addressing mechanism. This suite operates in a way that makes it look as if all broadcasts are received "simultane- ously" by all the members of a group, and are received in the same "view" of group membership. o Ways of obtaining distributed executions. When a request arrives in a group, or a distributed event takes place, ISIS supports any of a variety of execution styles, ranging from a redundant computation to a coordinator-cohort computation in which one process takes the requested actions while oth- ers back it up, taking over if the coordinator fails. o Replicated data with 1-copy consistency guarantees. o Synchronization facilities, based on token passing or read/write locks. o Facilities for watching a for a process or site (computer) to fail or recover, triggering execution of subroutines pro- vided by the user when the watched-for event occurs. If several members of a group watch for the same event, all will see it at the same "time" with respect to arriving mes- sages to the group and other events, such as group member- ship changes. o A facility for joining a group and atomically obtaining copies of any variables or data structures that comprise its "state" at the instant before the join takes place. The programmer who designs a group can specify state information in addition to the state automatically maintained by ISIS. o Automatic restart of applications when a computer recovers from a crash, including log-based recovery (if desired) for cases when all representatives of a service fail simultane- ously. o Ways to build transactions or to deal with transactional files and database systems external to ISIS. ISIS itself doesn't know about files or transactions. Everything in ISIS is fault-tolerant. Our programming manual has been written in a tutorial style, and gives details on each of these mechanisms. It includes examples of typical small ISIS applications and how they can be solved. The distribution of the system includes demos, such as the parallel make facility men- tioned above; this large ISIS application program illustrates many system features. To summarize, ISIS provides a broad range of tools, including some that require algorithms that would be very hard to support in other systems or to implement by hand. Performance is quite good: most tools require between 1/20 and 1/5 second to execute on a SUN 3/60, although the actual numbers depend on how big processes groups get, the speed of the network, the locations of processes involved, etc. Overall, however, the system is really quite fast when compared with, say, file access over the network. For certain common operations a five to ten-fold performance improvement is expected within two years, as we implement a col- lection of optimizations. The system scales well with the size of the network, and system overhead is largely independent of network size. On a machine that is not participating in any ISIS application, the overhead of having ISIS running is negligible. --- You can get a copy of ISIS in the near future --- A prototype of ISIS is now fully operational and is being made available to the public. The version we plan to distribute con- sists of a C implementation for UNIX, and has been ported to the SUN UNIX system, ULTRIX, the Gould UNIX implementation, and HP- UX. Performance is uniformly good. A 225 page tutorial and sys- tem manual containing numerous programming examples is also available. The remainder of this posting focuses on how to get ISIS, and how to get the manual. Everything is free except bound copies of the manual. Source is included, but the system is in the public domain, and is released on condition that any ports to other sys- tems or minor modifications remain in the public domain. The manual is copyrighted by the project and is available in hard- copy form or as a DVI file, with figures available for free on request. --- Release schedule --- June 1: a BETA release of the system for reasonably sophisti- cated sites that can deal with software that will probably still have some bugs. The system, as of June 1, will not scale beyond about 150 sites at one time. August 1: a final release of the June 1 system and a BETA release of a version containing some performance enhance- ments and some tools that are missing from the June-1 Beta release (notably, an interface from ISIS to transactional systems like CAMELOT). --- Release strategy --- We will place a compressed TAR image in a public directory on one of our machines and permit people to copy it off using FTP. Also available will be DVI format versions of our manual. Bound copies will be available at $10 each. A package of figures to glue into the DVI version will be provided free of charge. A tape containing ISIS will be provided to a limited number of sites upon payment of a charge to cover our costs in making the tape. Our resources are limited and we do not wish to do much of this. --- Commercial support --- We are working with a local company, ISIS Distributed Systems Inc., to provide support services for ISIS. This company will prepare distributions and work to fix bugs. Support contracts are available for an annual fee; without a contract, we will do our best to be helpful but make no promises. Other services that IDS plans to provide will include consulting on fault-tolerant distributed systems design, instruction on how to work with ISIS, bug identification and fixes, and contractual joint software development projects. The company is also prepared to port ISIS to other systems or other programming languages. Contact "birman@gvax.cs.cornell.edu" for more information. --- If you want ISIS, let us know --- Send mail to schiz@gvax.cs.cornell.edu, subject "I want ISIS", with electronic and physical mailing details. We will send you a form for acknowledging agreement with the conditions for release of the software and will later contact you with details on how to actually copy the system off our machine to yours. --- You can read more about ISIS if you like --- The following papers and documents are available from Cornell. We don't distribute papers by e-mail. Requests for papers should be transmitted to "schiz@gvax.cs.cornell.edu". 1. Exploiting replication. K. Birman and T. Joseph. This is a preprint of a chapter that will appear in: Arctic 88, An advanced course on operating systems, Tromso, Norway (July 1988). 50pp. 2. Reliable broadcast protocols. T. Joseph and K. Birman. This is a preprint of a chapter that will appear in: Arctic 88, An advanced course on operating systems, Tromso, Norway (July 1988). 30pp. 3. ISIS: A distributed programming environment. User's guide and reference manual. K. Birman, T. Joseph, F. Schmuck. Cornell University, March 1988. 275pp. 4. Exploiting virtual synchrony in distributed systems. K. Birman and T. Joseph. Proc. 11th ACM Symposium on Operating Systems Principles (SOSP), Nov. 1987. 12pp. 5. Reliable communication in an unreliable environment. K. Birman and T. Joseph. ACM Transactions on Computer Systems, Feb. 1987. 29pp. 6. Low cost management of replicated data in fault-tolerant distributed systems. T. Joseph and K. Birman. ACM Transac- tions on Computer Systems, Feb. 1986. 15pp. We will be happy to provide reprints of these papers. Unless we get an overwhelming number of requests, we plan no fees except for the manual. We also maintain a mailing list for individuals who would like to receive publications generated by the project on an ongoing basis. If you want to learn about the virtual synchrony as an approach to distributed computing, the best place to start is with refer- ence [1]. If you want to learn more about the ISIS system, how- ever, start with the manual. It has been written in a tutorial style and should be easily accessible to anyone familiar with the C programming language.
jsimellon@uunet.UU.NET (Larry Mellon) (05/23/89)
In article <5523@hubcap.clemson.edu>, ken@gvax.cs.cornell.edu (Ken Birman) writes: > In article <5512@hubcap.clemson.edu> landman@Sun.COM (Howard A. Landman) writes: > > >..... We are running massive gate-level simulations using > >simulator S on Sun workstations. We have two problems. (1) Our largest > >examples won't fit in 128 MB (maximum memory for the machines). (2) The > >simulation takes too long...... Is Linda a reasonable basis on which to > >build this system? > > While Linda probably IS a reasonable basis on which to build this > system, I want to suggest an alternative. > [...] > My group has developed a distributed computing technology called "ISIS" > that can be used to solve these kinds of problems, too. We believe that > ISIS has some important advantages over Linda in certain situations and > for certain architectures. (We are also convinced that Linda has > advantages over ISIS in some situations/architectures). > [...] > Offhand, I don't actually know of a 3rd approach that fits this > general framework, unless one includes Jefferson's time-warp work (you > simulation users will want to find out about that, too!) Hard to pass a lead-in like that! Jade Simulations International has developed a parallel simulation language based on David Jefferson's TimeWarp ('Virtual Time': ACM transactions on programming languages, 7(3), July 1885). This language, Sim++, is a superset of AT&T's C++, an object-oriented version of C. Sim++ allows you to develop and debug your simulations sequentially on a Sun workstation, using standard Sun tools, such as dbx, emacs, etc. Once your simulation is complete, it may be run in parallel across a network of Sun workstations or a high-speed multicomputer. No source code changes are required to execute in parallel. Currently, Sim++ runs on: - a single Sun3 workstation - a network of Sun3 workstations - the BBN Butterfly multicomputer (68020 based) - Meiko Transputer boards (RISC architecture) We are presently porting Sim++ to the Sun4 workstation, and several new multiprocessor systems. Jefferson's TimeWarp is intended to solve the problems of synchronizing simulation time across multiprocessors in the operating system, rather than in the user's code. It is best suited to descrete-event simulations; generally, the more compute time per event, the better your speedup. An incredibly brief description of TimeWarp follows. Basically, a simulation consists of entities which pass events between themselves, and take some action when an event is received. Each event has a time-stamp, which is when that event is to occur in simulation time. An entity acts on each event as soon as it is received, *with no attempt to verify that the event is in correct simulation time order*. This is called 'optimistic synchronization' by supporters, and 'silly' by opponents. Briefly, the rational is that if you verify the event order, you are wasting potential execution time and clogging your communication links with pointless queries. "But that's only true if the events happen to arrive in the correct order", the distractors cry in outrage. Well, true. That's why it's called optimistic, you see. If events arrive in order, we have a clear gain. If an entity happens to process an event at time X, then an event at time X-10 arrives, we simply 'rollback' the entity to a time before X-10, and start it up again. Thus, it will now process X-10, then X. "But, but, you've wasted processing time on event X!" stammer the distractors. Well, not really. If we had remained blocked until X-10 had arrived, that processing time was 'wasted' anyways. If fact, the worst case of TimeWarp, where all events arrive out of order, is exactly equivalent to the 'conservative' synchronization method; where entities remain blocked until event order has been verified. "And what is this 'rollback'?" you ask? That's a tricky one. While an entity is excuting, snapshots of it's state are taken from time to time. A snapshot consists of all static and automatic variables and events sent or received by the entity. A rollback consists of restoring an entity to one of it's previous states. Now, before everybody jumps on me, there are many things about TimeWarp I have not said, and details I have left vague. Please read Jefferson's paper; it is far better than anything I can write on the fly. I have other references as well, send email for a list. To people of the 'conservative mechanism' ilk: I concede there are applications better suited for conservative synchronization than TimeWarp, so please, no hate mail. I will go out on a limb and state that current research shows that optimistic beats out conservative in the general case. If you have any questions regarding Sim++ or TimeWarp, please contact me via email or telephone. Larry Mellon <jsimellon@cpsc.ucalgary.ca> Jade Simulations International (403) 282-5711
jerbil@csvax.caltech.edu (Stainless Steel Gerbil [Joe Beckenbach]) (05/25/89)
Larry Mellon writes a quick overview of TimeWarp-type optimistic simulators. This is not to jump on him at all about this (it's not his fault :-) but to voice the opinion of a current 'detractor'. > To people of the 'conservative mechanism' ilk: I concede there are >applications better suited for conservative synchronization than TimeWarp, >so please, no hate mail. No problem by me, Larry. If there's any hate mail about this posting, send it to me. Better yet, answer my objections [or what you perceive as my objections]. In his article <5573@hubcap.clemson.edu> Larry Mellon writes: > Jefferson's TimeWarp is intended to solve the problems of synchronizing >simulation time across multiprocessors in the operating system, rather >than in the user's code. It is best suited to descrete-event simulations; >generally, the more compute time per event, the better your speedup. It seems to me that a discrete-event simulator need not have the user concern himself with simulation time at all, other than to print out its value in reports partway through the simulation process. The speed-up comes from assuming that one processor is given only one simulator node to work with, is the impression that I get from reading some papers and talking with the people here, including one who gave one of the few pro-conservative-simulation results in the Miami conference on simulation (1989 Distributed Simulation Conference). > Basically, a simulation consists of entities which pass events >between themselves, and take some action when an event is received. >Each event has a time-stamp, which is when that event is to occur >in simulation time. An entity acts on each event as soon as it is >received, *with no attempt to verify that the event is in correct >simulation time order*. This is called 'optimistic synchronization' >by supporters, and 'silly' by opponents. Briefly, the rational is that if >you verify the event order, you are wasting potential execution time >and clogging your communication links with pointless queries. > "But, but, you've wasted processing time on event X!" stammer >the distractors. Well, not really. If we had remained blocked until >X-10 had arrived, that processing time was 'wasted' anyways. If fact, >the worst case of TimeWarp, where all events arrive out of order, is >exactly equivalent to the 'conservative' synchronization method; >where entities remain blocked until event order has been verified. > "And what is this 'rollback'?" you ask? That's a tricky one. >While an entity is excuting, snapshots of it's state are taken from >time to time. A snapshot consists of all static and automatic variables >and events sent or received by the entity. A rollback consists of >restoring an entity to one of it's previous states. Translation: project as far into the future as you can, while still being able to save all your state information. If you receive something 'out-of-order', step back to the right spot, process the new event, and start processing all events 'after' it but received before it. This entails saving all the state information and the timestamped event notifications, using a very large amount of memory if you wish to be sure that your simulation is valid. One paper reputedly at the conference shows the type of simulation which fits this set of constraints well: a simulated pool game, with a processor assigned to a square area of the table. In my honest opinion, this `toy' shows the best way to use TimeWarp: absolute minimal changes in state [eg a billiard ball hits another, or a bumper, or changes processors only occasionally compared to sitting still or rolling unimpeded]. I'm not so sure that this is a livable constraint for most simulations. For instance, gate-level VLSI simulations lose in TimeWarp. [Not only that, but the potential parallelism would not be realized except minimally.] The notion of one blocked process wasting processor time implies strongly that TimeWarp is based on a one process per node model of computation. That constraint keeps potential parallelism potential, and as such is not of any interest to me. Again, my honest opinion, TimeWarp seems to be doing half-measures in parallelizing a simulation: * If it needed to be parallel in only a few pieces, why not let the user write the synchronization, or supply libraries to support it? Surely the interactions can be understood well enough at that level. * If it can parallelize to many pieces, why not go the whole hog and multi- process on the different physical nodes [either truly, or via light- weight processes]? This hides the communnication overhead, and answers the objection about 'wasting processor time'. > I will go out on a limb and state that current research shows that >optimistic beats out conservative in the general case. And I will go out on the other limb and state that current research I have seen, including Wen-King Su's paper (presented at Miami, titled "Variants of the Chandy-Misra-Bryant Distributed Discrete-Event Simulation Algorithm"), would demonstrate that conservative simulation is more widely usable than optimistic simulation, given a range of machine hardware, distributed environments, and simulations. My caveats and speculations on this particular limb: C1) I know of no paper directly comparing two different implementations of a collection of simulations, or even a single simulation, where one is a conservative and one an optimistic, with hard result such as run times, simulation sizes, data variation, usage of resources, and agreement of results with a standard sequential implementation of that simulation. S1) The more inherent parallelism a problem has, the less amiable it will be to optimistic simulation due to each event-causing 'object' being an independent source of events not in the predicted stream of a TimeWarp process. S2) My experience with simulation is on hardware running sequential and message-passing operating systems under the simulation user code. TimeWarp might indeed be much better suited for shared-memory machines, but then physical limitations keep the number of parallel physical nodes to some low number. References to performance comparison papers, or even good papers on the implementation of TimeWarp, are welcome! The definitive experiment would pit several implementations of simulations over this matrix: [ sequential, conservation, optimistic ] x [ qualitatively-varied suite of simulations ] x [ machines on which all implementations can run ] x [ measures of performance (time, result correctness, etc) ] Joe Beckenbach PS Are there any good grad schools out there with professors interested in simulation in general, preferably with a Software Engineering option and no firm entrenchment of either optimistic or conservative simulation? I'm considering what I want to do with my next few years. :-) -- Joe Beckenbach | jerbil@csvax.caltech.edu | This plot for cultivation of Caltech 256-80, Pasadena CA 91125 | a fertile imagination.