They Invented What? (No. 213)

U.S. Pat. No. 7,246,054: Discrete event simulation system and method.

JW Note:  Many thanks to Patrick Anderson at the Gametime IP blog for bringing this one to our attention.  Patrick opines that, although the patent uses very serious language, the crux of the claims deal with time travel in a simulation to avoid violating a causality constraint.  Enjoy!

What is claimed is:

1. A method of performing a simulation using a plurality of processing entities, each of the plurality of processing entities maintaining a respective one of a plurality of queues, each of the plurality of queues adapted to store a respective plurality of future events to be processed, each of the plurality of queues having an associated simulation time recording a time of the simulation as events are processed, the method comprising:  establishing, for each of the plurality of future events in each queue, a respective virtual look-back time defining an earliest simulation time wherein processing any event having a timestamp later in time will not violate a causality constraint for a respective one of the plurality of future events for which the virtual look-back time is established; and selecting events to be processed from the plurality of queues based, at least in part, on respective virtual look-back times.

2. The method of claim 1, wherein the virtual look-back time is determined as the simulation time of the associated queue minus a look-back window established for each of the plurality of events.

3. The method of claim 2, wherein selecting events from the plurality of queues includes processing events in parallel, each of the plurality queues processing respective stored events in order from earliest virtual look-back time to latest virtual look-back time.

4. The method of claim 3, further comprising receiving, at one of the plurality of processing entities, a straggler event from another of the plurality of processing entities, the straggler event having a timestamp earlier than the simulation time of the queue of the one of the plurality of processing entities that received the straggler event.

5. The method of claim 4, further comprising, comparing the timestamp of the straggler event with the virtual look-back time of events processed by the one of the plurality of processing entities that have timestamps later in time than the timestamp of the straggler event.

6. The method of claim 5, wherein comparing includes identifying each processed event for which the timestamp of the straggler event is earlier in time than the virtual look-back time of the corresponding processed event.

7. The method of claim 6, further comprising rolling back each identified event for which the timestamp of the straggler event is earlier in time than the virtual look-back time of the corresponding processed event.

8. A computer-readable medium having computer-readable signals stored thereon that define instructions that, as a result of being executed by a computer, instruct the computer to perform a method of performing a simulation using a plurality of processing entities, each of the plurality of processing entities maintaining a respective one of a plurality of queues, each of the plurality of queues adapted to store a respective plurality of future events to be processed, each of the plurality of queues having an associated simulation time recording a time of the simulation as events are processed, the method comprising: establishing, for each of the plurality of future events in each queue, a respective virtual look-back time defining an earliest simulation time wherein processing any event having a timestamp later in time will not violate a causality constraint for a respective one of the plurality of future events for which the virtual look-back time is established; and selecting events to be processed from the plurality of queues based, at least in part, on respective virtual look-back times.

9. The computer-readable medium of claim 8, wherein the virtual look-back time is determined as the simulation time of the associated queue minus a look-back window established for each of the plurality of events.

10. The computer-readable medium of claim 9, wherein selecting events from the plurality of queues includes processing events in parallel, each of the plurality queues processing respective stored events in order from earliest virtual look-back time to latest virtual look-back time.

11. The computer-readable medium of claim 10, further comprising receiving, at one of the plurality of processing entities, a straggler event from another of the plurality of processing entities, the straggler event having a timestamp earlier than the simulation time of the queue of the one of the plurality of processing entities that received the straggler event.

12. The computer-readable medium of claim 11, further comprising, comparing the timestamp of the straggler event with the virtual look-back time of events processed by the one of the plurality of processing entities that have timestamps later in time than the timestamp of the straggler event.

13. The computer-readable medium of claim 12, wherein comparing includes identifying each processed event for which the timestamp of the straggler event is earlier in time than the virtual look-back time of the corresponding processed event.

14. The computer-readable medium of claim 13, further comprising rolling back each identified event for which the timestamp of the straggler event is earlier in time than the virtual look-back time of the corresponding processed event.