Next-Event Time Advance and the Simplicity of the Priority Queue

The defining operation of a discrete-event simulator is not a computation of the state but a jump through time. Between events nothing changes, so the simulator does not advance in fixed steps; it jumps from the current event to the earliest future event, applies that event’s consequences, and jumps again. The entire mechanism is a priority queue of pending events, and the subtle part is not the jump itself but what happens when two events are scheduled for the same instant.

Why time advances by events and not by steps

A fixed-increment clock must decide how small the increment is. Too large and simultaneous events within one step are processed in an arbitrary order that can change the outcome; too small and the simulator spends most of its time processing empty steps. The next-event approach eliminates the choice by advancing to exactly the next time at which the state can change, so no computation happens between events and no two distinct event times are collapsed into one step.

The state changes only at event times, and between them it is constant. This is the modeling assumption that makes discrete-event simulation tractable: the state is a piecewise-constant function of time, the events are the jump points, and the queue of pending events is the complete description of the future given the current state. When an event fires, it may cancel, reschedule, or create other events, and the simulator updates the queue accordingly before jumping again.

The advantage is asymptotic efficiency. A simulator of a system with one event per unit time on average performs one queue operation per event, and the number of operations is proportional to the number of events, not to the number of clock ticks. A fixed-step simulator of the same system needs a step small enough to resolve the closest pair of event times, and the step count is the reciprocal of the resolution rather than the event count.

The heap that stores the future

The pending events are stored in a priority queue ordered by event time, and the next event is the minimum. A binary heap gives $O(1)$ access to the minimum and $O(\log n)$ insertion and removal, where $n$ is the number of pending events, and it is the default because the event count can be large: a network of queues each holding a few scheduled events produces a heap whose size is the number of active entities, not the number of events processed over the run.

The heap invariant is that every parent is no later than its children, which makes the root the earliest event. Inserting a new event appends at the bottom and sifts it up past any earlier events; removing the minimum takes the root, moves the last element into its place, and sifts it down past any later children. Both operations are logarithmic in the size, and the constant is small enough that the heap rarely dominates the cost of the events themselves, which usually involve random variate generation.

import heapq

class Event:
    __slots__ = ('time', 'order', 'kind', 'payload')
    def __init__(self, time, order, kind, payload):
        self.time, self.order, self.kind, self.payload = time, order, kind, payload
    def __lt__(self, other):
        # Earlier time wins; ties broken by insertion order.
        return (self.time, self.order) < (other.time, other.order)

pending = []                    # a heap of Event objects
heapq.heappush(pending, Event(3.0, 0, 'arrival', None))
heapq.heappush(pending, Event(3.0, 1, 'departure', None))

The tuple comparison carries the tie-breaker: two events at the same time are ordered by their insertion order, so the one that was scheduled first fires first. This is not an arbitrary choice but a statement of the model’s semantics, and it has to be made before the run, because the order in which simultaneous events fire can change the final state.

Simultaneity is a modeling decision, not an accident

When two events are scheduled for the same instant, the simulator must choose an order, and the choice is part of the model. The three standard policies are: a fixed priority by event type, first-in-first-out by scheduling time, and an arbitrary but deterministic order such as a secondary key. Each policy produces a different trajectory when the two events interact, and the differences are real: an arrival and a departure at the same instant, processed arrival-first, leaves the queue at a different length than departure-first.

The danger is not the tie but the hidden dependence on it. A heap that orders ties by memory address, or by a floating-point comparison that treats $3.0$ and $3.0$ as equal, produces an order that depends on the insertion sequence and possibly on the allocator, which makes the run non-reproducible across platforms. A simulator that reports the same mean but a different path on different machines has a tie-breaking bug, and the bug is silent because the mean is insensitive to the exact tie order in many models.

The cleanest rule is a total order on events. Every event carries its time and a monotonically increasing sequence number, and the heap compares the pair, so the order is deterministic and reproducible from the seed alone. The sequence number is assigned at scheduling time and never reused, so two events that happen to coincide are ordered by which was scheduled first, which reflects the causal structure of the simulation rather than an arbitrary address.

Event time is not real time, and the distinction matters

A discrete-event simulator advances a simulated clock that is unrelated to the wall clock. The simulated clock jumps from event to event, and a run that simulates a year of operation may finish in a second of wall time if the events are sparse, or in an hour if every event triggers expensive computation. The two clocks are connected only by the number and cost of the events, and a simulator’s performance is measured in events per second, not simulated time per second.

The decoupling creates two failure modes. A model that schedules an event at every epsilon of simulated time, rather than only at the times the state changes, is a fixed-step model wearing a next-event clock, and it loses the efficiency advantage without gaining accuracy. A model whose event rate depends on the state, such as a queue near saturation whose departure rate matches its arrival rate, can produce an event count that grows without bound as the load approaches one, and the run time is proportional to that count.

def run(pending, horizon):
    now = 0.0
    count = 0
    while pending and now < horizon:
        ev = heapq.heappop(pending)
        now = ev.time
        count += 1
        # apply the event; it may push new events onto `pending`
    return count

The loop pops the earliest event, advances the clock to its time, and applies it. The clock moves monotonically forward because the heap always returns an event at or after the current time, and the monotonicity is what allows the run to be resumed and replayed from any checkpoint: the future is a function of the current state and the remaining heap.

Cancellation, and why the heap must support it

An event that is no longer valid when its time arrives must be cancelled, and cancellation is the operation that a naive heap does not support. The standard pattern is lazy deletion: mark the event as cancelled when the cause is known, and skip it when it reaches the top of the heap. The heap grows by the number of cancelled events, which is bounded by the number scheduled, and the cost is the occasional skipped pop rather than a search through the heap.

The alternative is to give every event an identity and keep an index from identity to heap position, so cancellation is a decrease-key or delete operation that runs in $O(\log n)$. This is what a simulator needs when events are cancelled in bulk, as when a server failure invalidates every departure scheduled for that server. The lazy pattern is simpler and correct; the indexed pattern is faster when the cancellation rate is high, and the choice is a real engineering trade in a simulator that models failure and repair.

A skipped cancellation is also the simplest source of a subtle correctness bug: if a cancelled event is not checked before it fires, it changes the state once more than the model intends, and the error propagates into every subsequent statistic. The check must happen at the pop, not at the schedule, because the cancellation may occur after the event is scheduled but before it fires.

The priority queue is the shared core of the whole mechanism, and its correctness is what the rest of the simulator rests on. The birth-death analysis gives the closed form that a queue simulator is verified against, and the square-root convergence governs how many replications the verification needs before the measured mean is close to the known one.