Virtual Time II: Storage Management in Distributed Simulation

Abstract

The main contribution of this paper is the Cancelback Protocol, an extension of the Time Warp mechanism that handles storage management. It includes both fossil collection, the recovery of storage for messages and states that can never again influence the computation, and cancelback, the recovery of storage assigned to messages and states at times so far in the future that their memory would be better used for more immediate purposes. It guarantees that Time Warp is optimal in its storage requirements when run in shared memory, i.e. Time Warp will successfully complete a simulation using no more space than it would take to execute the same simulation with the sequential event list algorithm. This is better by a factor of two than the only previously published result. Without this protocol (or equivalent) Time Warp’s behavior can be unstable; hence it should be considered an essential part of Time Warp mechanism, rather than simply a refinement. In addition we also prove that asynchronous conservative algorithms, including all of the Chandy-Misra-Bryant (CMB) mechanisms, are not optimal; they cannot neces-Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1990 ACM-0-89791-404-X/90/0008/0075 $1.50 sarily execute a simulation in the same amount of space as a sequential execution. In some cases a simulation requiring space n+k when executed sequentially might require O(nk) space when executed on n processors by CMB. 1.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 51 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.