Global Virtual Time (GVT)

Global Virtual Time (GVT) is the minimum timestamp among all unprocessed and partially processed events in an optimistic parallel discrete event simulation. It represents a lower bound on the timestamp of any future rollback. Formally, at wall-clock time t, GVT(t) = min{ LVTs of all LPs, timestamps of all messages in transit }. No event with a timestamp less than GVT will ever be scheduled or rolled back, making GVT the commit horizon for the entire distributed simulation.

GVT enables fossil collection, the process of reclaiming memory occupied by historical state vectors and event logs. Key properties:

• Any state saved with a timestamp less than GVT is eligible for deletion, as rollback to that point is impossible.
• Anti-messages for events older than GVT can be discarded, as their corresponding positive messages are guaranteed delivered.
• Without accurate GVT computation, memory consumption grows unbounded, eventually causing simulation failure.
• Efficient fossil collection is critical for long-running simulations of supply chain networks spanning millions of events.

GVT defines the point of no return for operations that cannot be rolled back:

• I/O Commit: Output events (e.g., triggering a physical warehouse robot command) can only be released to external systems when their timestamp is less than GVT.
• Database Writes: Persistent state changes in a digital twin's backing store are committed only when GVT advances past the corresponding virtual time.
• Checkpointing: Consistent global snapshots are taken at GVT boundaries, ensuring recoverability without causal violations.
• This property is essential for hardware-in-the-loop supply chain simulations where simulated decisions trigger real-world actuation.

Several distributed algorithms compute GVT with varying trade-offs:

• Samuelson's Algorithm: A synchronous, centralized approach where a controller collects local virtual time reports and computes the global minimum. Simple but introduces blocking overhead.
• Mattern's Algorithm: Uses consistent cuts and message acknowledgment rounds to compute GVT asynchronously without halting event processing.
• Fujimoto's Shared Memory Approach: Exploits hardware shared memory in multiprocessor systems for low-latency GVT updates via atomic operations.
• Transient Message Problem: All algorithms must account for messages in flight whose timestamps may be lower than any logical process's reported local time, requiring message acknowledgment protocols.

GVT advancement rate directly measures simulation progress. If GVT stalls, the simulation cannot commit new events, leading to livelock. Common causes of stalled GVT:

• Straggler events with extremely low timestamps that prevent the global minimum from advancing.
• Lookahead starvation, where logical processes cannot predict future event times, forcing conservative GVT estimates.
• Network latency in distributed deployments delaying transient message accounting.
• Monitoring GVT progression is a key observability metric for large-scale digital twin simulations, often visualized as a monotonically increasing step function.

GVT is the foundational synchronization mechanism for the Time Warp optimistic protocol, invented by David Jefferson in 1985. In Time Warp:

• Logical processes speculatively execute events without waiting for causality guarantees.
• Upon receiving a straggler message with a timestamp earlier than the local clock, the process rolls back to a prior state and re-executes.
• GVT provides the safety net that bounds rollback depth and enables fossil collection.
• The efficiency of Time Warp depends critically on GVT computation frequency: too frequent wastes resources, too infrequent risks memory exhaustion. Adaptive algorithms dynamically tune the GVT interval based on rollback frequency and memory pressure.