Time Warp: Operating system that implements process rollback. Time Warp is appropriate when applications use an artificial time scale (like simulations). It might be the only choice for apps that require virtual time synchronization. Assuming that processes communicate via (virtual-)timestamped messages, we have to assure that messages are delivered in order. However, we can never be sure that we've received "the next" message. (The virtual-timestamp may be a real number). So, "how can the OS control the execution of a process so that it receives its messages in nondecreasing timestamp order and is guaranteed to make progress?" * Rollback Using process rollback, the paper solves this problem. It optimistically assumes the next highest timestamped message in the queue is really the next message. If later, this turns out to not be the case, the process is rolled back, and the messages are reprocessed. * Messages, Anti-messages and Annhiliation - The system is implemented using a system of messages and anti-messages. Anti-messages have all the same field values as messages, but have opposite signs. - Sending a message actually generates a message/anti-message pair. The positive message is delivered to the receiver's input queue, and the negative message is collected in the sender's output queue (to be used in case of rollback). - When a message and its antimessage are inserted into a queue, they annhiliate each other, and the queue length gets shorter. - When a process starts moving forward again, after rollback, any duplicate messages it sends are annhiliated by the antimessages already in its output queue (remaining from the last execution). Any negative message in the output queue that is not annhiliated must be canceled--that is its side effects at the receiver must be undone. * Advantages over Chandy-Misra The main advantage of TimeWarp over Chandy-Misra is: 1. TimeWarp doesn't require a static communication network between processes. Processes can send messages to any other process. 2. Processes can send messages to other processes without respecting message ordering, for example,