Discrete-event simulation (DES) vs system dynamics (SD)

Types of models in computer simulations

• Agent-Based Model (ABM)
• System Dynamics (SD)
• Discrete-Event Simulation (DES)

DES is computationally efficient, since it jumps from event to event, instead of between small timesteps.

Events in DES are not separated by a constant time span, and can instead be separated by hugely varying time spans. DES jumps directly from one event to the next, without having to run many simulation loops between two events.

You can also model ABMs with an event loop, but usually I use a short time step instead, like in a real-time game engine.

Discrete-event simulation (DES)

This is an example of a Docker cluster that is hosting a website.

• The Docker cluster starts at one Docker instance.
• There is a flow of visitors to the website: 6 visits per second ± some randomization.
• Each request takes 2 seconds to finish ± some randomization.
• A Docker instance can serve max 10 visitors concurrently.
• A single Docker instance can't serve all incoming requests in enough time.
  • Little's law: $6 * 2 = 12 \text{ visitors need to be served concurrently on average}$, which is larger than the 10 visitors that a single Docker instance can handle.
• The Docker cluster supports autoscaling: it periodically adds/removes Docker instances to/from the cluster, allowing more concurrent visitors.

This demonstrates a common scenario that happens during a cache stampede, or when a website receives a large traffic spike suddenly.

The HTTP requests pile up until the Docker cluster has had enough time to notice that server loads are high. Then the Docker cluster spawns a new Docker instance, so that there are two instances serving requests, giving the cluster a capacity of serving 20 requests concurrently.

Sometimes the average load is still so high that the cluster spawns a third Docker instance. This gives us a capacity of 30 concurrent requests, which is a lot more than the 12 that we need. Therefore, the Docker cluster eventually removes this third Docker instance from the cluster. This up-and-down pattern can be observed often in real life Docker clusters.

From the below graph we can see the latencies between different events of the DES model.

Notice the difference between the average and maximum latency between visit_site --> http_request_accepted. When there was only one Docker instance available, HTTP requests had to queue for a long time.

From the graph below, we can see the causal relationships between the DES model's events (blue rectangles) and state variables (orange ellipses).

The numbers on the edges show how many times an event scheduled another event, or how many times an event read/wrote data from/to a state variable.

System dynamics (SD)

I tried to simulate the above scenario in system dynamics as well.

I couldn't quite get the same numbers out of this model as I did from the DES model above.

I also had to use a lot of time trying to get the model to do what I want.

• Either this scenario has way too few entities and too many detailed rules in it to be easily modelable in DS...
• ...or I don't find the calculus-like thinking (integration) of SD intuitive...
• ...or I don't have enough experience constructing SD models, unlike DES/ABM models...
• ...or all of the above.

You can find from the SD code below that it's simpler than the DES code, but I had to think about the math expressions a lot more than I did with DES. With DES, I just create the rules inside event handlers, which I found a lot easier to do.

Therefore, I think DES and ABM are the way to go for me currently. It's just much easier to model the actual, discrete rules of events or agents, and see what kind of behavior emerges.

SD probably becomes easier when you're trying to create a more coarse-grained model. Here is a common population cycle example in SD:

Agent-based model (ABM)

I didn't model the Docker cluster example with ABM, because it would look quite similar to the DES model.

The difference would probably be that each agent would have its own state (resulting in more code), whereas DES relies more on global/aggregate state (resulting in less code).

In ABM, I could have e.g. these agents:

• VisitorAgent
  • requestStartTime
  • requestFinishTime
  • step() is run often enough that it creates 6 new HTTP request every minute
    • Runs DockerClusterAgent.addRequest() directly, or sends a message to DockerClusterAgent via the simulation's event mechanism
• DockerClusterAgent
  • instances: DockerInstanceAgent[]
  • addRequest() sends the request to an instance in instances
  • step()
    • Runs autoscaling every 60 minutes to see if the cluster should add or remove Docker instances
    • Runs HTTP request processing whenever the VisitorAgent sends a new request
    • Runs HTTP response handling whenever a request has been processed and sent to the VisitorAgent
• DockerInstanceAgent
  • httpServerCapacity: Resource handles queuing of requests if there are no free slots left
  • step() reserves httpServerCapacity whenever there's a new HTTP request, and frees httpServerCapacity when an existing request finishes processing

ABM simulation loop alternatives

As I mentioned in the beginning of this article, you can model an ABM with two kinds of loops:

• Tick-based: for (let time = 0; time < end; time += timeStep)
• Event-based: for (const event of eventQueue)

Alternative 1: tick-based ABM

for (let time = 0; time < end; time += dt) {
  for (const agent of agents) {
    agent.step(time, dt);
  }
}

class Agent {
  step(time, dt) {
    // ... do agent-specific logic ...
  }
}

This is the simplest loop, but it may result in lots of no-op calls to agent.step(), wasting compute resources.

Not all agents may need to do stuff in every frame, depending on what kind of a simulation you're doing.

In a real-time ABM with floating point x/y/z coordinates per agent, you might want to do this, so that you can be sure that you're modeling intricate inter-agent dynamics.

But in a much more coarse-grained ABM, running agent.step() for all agents in every loop iteration is wasteful. For example, in the Docker cluster example above, the "autoscaling agent" only needs to act once per 60 seconds. On the other hand, each Docker instance needs to act much more often: when a request arrives to the instance, the instance needs to check if the HTTP server has any available slots for processing the request.

Therefore, the "autoscaling agent" would need to do something like this:

class AutoScalingAgent extends Agent {
  lastExecutionTime = 0

  step(time, dt) {
    if (time - this.lastExecutionTime >= 60) {
      this.lastExecutionTime = time;
      this.autoscale();
    }
  }
}

If many agents need to keep track of earlier execution times (or "events") in that way, an event-queue-based ABM may be a better choice.

Alternative 2: event-queue-based ABM

This is basically an ABM where every agent is its own DES model. The agents coordinate via a global event queue.

while ((event = eventQueue.dequeue()) {
  time = event.time;
  event.agent.step(time);
}

class Agent {
  step(time) {
    // ... do agent-specific logic ...

    // Loop. Each agent handles its own "tick rate".
    // The game engine doesn't force the same tick rate for all agents.
    // For example, this agent acts once every 5 seconds.
    eventQueue.schedule(this.step, 5);
  }
}

An "autoscaling agent" would look much simpler than in the tick-based ABM:

class AutoScalingAgent extends Agent {
  step(time) {
    this.autoscale();
    eventQueue.schedule(this.step, 60);
  }
}

The downside is that you can't animate the simulation in real-time (e.g. at 30 fps) for the user. You can basically only jump from one event to the next in varying-length time slices.

Alternative 3: hybrid ABM (tick + event queue)

Apparently it's common in existing COTS simulation software to use a hybrid model. You basically split the engine into two loops, like in game engines: a render loop and a simulation loop.

• Render loop: The main loop iterates with a (fixed-size or varying) tick length, $dt$.
  • This allows you to animate the simulation (e.g. at 30 fps).
• Event loop: Each agent is a DES that schedules events for its actions.
  • This allows you to only run agent.step() when an agent actually wants to do something.

For example:

for (let time = 0; time < end; time += dt) {
  const frameEndTime = time + dt;
  const eventsInFrame = eventQueue.dequeueUntil(frameEndTime);

  for (const event of eventsInFrame) {
    time = event.time;
    event.agent.step(time);
  }

  // ... optionally run a render() method here, like game engines do ...
}

class AutoScalingAgent extends Agent {
  step(time) {
    this.autoscale();
    eventQueue.schedule(this.step, 60);
  }
}

TL;DR

• Use tick-based looping when your simulation is not huge, and you're OK with wasting CPU cycles.
• Use event-based looping when you don't need to render the simulation in real-time.
• Use a hybrid model if your simulation is huge, and you need to render it in real-time.

Notes

I created these models with roughly 60% vibe coding (ChatGPT canvas), and 40% fixing and tweaking by hand.

I used the following JS libraries:

• Chart.js
• viz-js

Browsers can nowadays use import statements without a build system, even from external URLs! For small scripts and even apps, you don't necessarily need a build system at all — that is, if you're OK with others seeing your full source code.

For example:

index.html:

<script type="module">
  import { DesModel } from './src/DesModel.js';

  // ... use DesModel ...
</script>

DesModel.js:

import * as Viz from 'https://cdn.jsdelivr.net/npm/@viz-js/viz@3.24.0/+esm';
import { Chart, registerables } from 'https://cdn.jsdelivr.net/npm/chart.js@4.5.1/+esm';

// ... code ...

Code

Parameters

DES code

SD code

SD code, simpler example