A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for executing components in a computing system, each said component executing instructions to perform computations, store a component state, and send and receive data messages to and from other components and to and from locations external to the system, said method steps comprising:
- including a virtual time (“VT”) timestamp within every message sent or received by any component;
- maintaining a “current virtual time” within each component by updating the component whenever messages are received and sent;
- and
- generating the VT timestamp for messages received from the locations external to the system, based upon their actual arrival time, and logging said messages to said non-volatile memory storage;
- computing, within a component, an updated current VT timestamp when a component sends a message;
- said updated current VT being the sum of the current VT and a delta-VT, where the delta-VT is a deterministically computed numeric value representing an approximate execution time for the computation since current VT was last updated;
- assigning as the VT timestamp of the sent message the sum of the updated current VT and a delay estimate, where the delay estimate is a deterministically computed numeric value representing an approximate communications delay before said sent data message arrives at the receiving component;
- computing a silence interval in the sending component, where the silence interval indicates a range of virtual time values that the sending component will avoid sending data messages;
- communicating from a sending component to said other components a silence message including said silence interval;
- generating a unique arrival order of received data messages at receiving components by using the VT timestamps, and exploiting the silence intervals to determine when to execute a receiving component waiting for the message with the next earliest VT timestamp;
- tracking a state of a component during program execution;
- intermittently storing said state as a checkpoint to an associated non-volatile storage device;
- and
- responding to failures by restoring the state of failed components to a previous VT, using a checkpoint on said associated non-volatile storage, and re-executing components, re-delivering messages sent from external locations between said previous VT and the time of failure by retrieving them from the log saved on said associated non-volatile memory storage device,
- wherein given said logging or deterministically computing said timestamps, said re-executing includes reproducing identical states and identical messages for all computations between the time of the checkpoint and the time of the failure.