Virtual time

Reviewer: Michael J. Manthey

This is a conceptually interesting paper which describes what appears to be an elegant and efficient solution to problems of synchronization, error recovery, and the realization of atomic actions in all kinds of distributed systems. The author states in his Introduction: Most distributed systems (including all those based on locks, semaphores, monitors, mailboxes, rendezvous, etc., and the usual mechanisms of flow control) use some kind of block-resume mechanism to keep processes synchronized. In addition, some systems divide a computation into discrete atomic actions, called transactions, and allow abortion-retry, essentially a form of rollback where rollback is only possible to the beginning of the current transaction. In contrast, the distinguishing feature of Time Warp [the implementation of virtual time] is that it relies on general lookahead-rollback as its fundamental synchronization mechanism. Each process executes without regard to whether there are synchronization conflicts with other processes. Whenever a conflict is discovered after the fact, the offending process(es) are rolled back to the time just before the conflict, no matter how far back that is, and then executed forward again along a revised path. Both the detection of synchronization conflicts and the rollback mechanism for resolving them are entirely transparent to the user. Virtual time is a “global one-dimensional temporal coordinate system imposed on a distributed computation.” The (“current” floor value of the) Global Virtual Time (GVT) can be broadcast occasionally by an algorithm which is linear in the delay, so no global time variable is necessary. Messages are processed locally in the order specified by the virtual receive time stamped on the message by the sender. (The author does not give any algo- rithm or heuristic by which this value might be calculated, which may be a stum- bling block in actual implementations.) If a message arrives whose virtual rece- ive time stamp is earlier than any message already processed, all the proce- ssed messages after that time must be undone. The mechanism by which this is done is to send anti-messages, which are “negative” copies of previously sent messages, chasing after their counterparts. Messages and antimessages annihilate each other whenever they cooccur in an input queue. The rollback so initiated does not, however, undo work already done into the indefinite past, but rather only back to the GVT value, which is chosen to always lag behind any possible local virtual time. Since nonreversible actions such as I/O are never performed before GVT has passed, the virtual time and antimessage scheme suffices even for these and similar situations, such as error recovery. The virtual time approach requires that all entities in the system be objects, and communicate only via messages; for example, database records must individually respond to, e.g., Read and Update messages. Three issues were left hanging in this reader's mind: (1)Is the algorithm by which senders stamp outgoing messages with a virtual receive time really so trivial as to deserve virtually no discussion__ __ It would seem that a poor choice of time scales between different processes could cause numerous pointless rollbacks. (2)In spite of the fact that GVT distribution is linear in the delay, this does not address the issue of whence the GVT value comes, which presumably also requires some message traffic. If not, there is no discussion of piggy-backing schemes. (3)Is there any formal statement of the Time Warp mechanism which can be expected to produce proofs that it indeed delivers the behavior promised by the textual arguments__ __ In spite of these cavils and the apparent complexity of the scheme, the author succeeded in convincing this reviewer that virtual time and the Time Warp mechanism are a likely paradigm for most, if not all, distributed systems, and as such deserve serious consideration.