Queueing Theory for Engineers

A quick reference for the queueing concepts used in the Node.js Event Loop M/G/1 Simulator post. An M/G/1 queue models random independent arrivals, varied processing times, and one server.

---

The M/G/1 notation (Kendall notation)

Queueing models are often written as A/B/c, where each letter describes a property of the system:

Position	Symbol	Meaning
A	M	Distribution of inter-arrival times (time between consecutive requests)
B	G	Distribution of service times (time to process one request)
c	1	Number of servers (in this case, one event loop thread)

So M/G/1 means:

• M — arrivals follow a Markovian (memoryless) process
• G — service times follow a general distribution (any shape)
• 1 — exactly one server

---

What each term means

Arrival rate ($\lambda$)

The average number of requests arriving per unit of time. Usually expressed in requests per second (RPS).

If 100 requests arrive in one second, $\lambda = 100$.

---

Inter-arrival time

The time gap between two consecutive arrivals. If arrivals are random and independent, this is often modeled as an exponential distribution.

For a Poisson process with rate $\lambda$, the average inter-arrival time is $1 / \lambda$.

---

Markovian (memoryless)

A process is Markovian when the future depends only on the present state, not on the past. In queueing theory, this usually means arrivals are modeled as a Poisson process.

Why it matters: The probability that the next arrival happens in the next second is the same no matter how long you have already waited. The system "forgets" its history.

---

Poisson process

A model for random, independent events occurring at a constant average rate. Examples:

• requests hitting an API endpoint
• customers arriving at a checkout
• packets arriving at a network interface

Key property: the number of arrivals in any fixed time interval follows a Poisson distribution.

---

Service time ($S$)

Service time is the time it takes the server to process one request from start to finish.

In the event loop analogy, this is the time between when a callback starts executing and when it finishes executing — including any synchronous work it does.

The mean service time $E[S]$ is the average of all service times.

---

General distribution (G)

The G in M/G/1 means the service time can follow any probability distribution — exponential, uniform, bimodal, or a heavy-tailed distribution where most requests are fast but a few are very slow.

This is what makes M/G/1 more realistic (and more mathematically interesting) than M/M/1, which assumes exponential service times.

---

Utilization ($\rho$)

Utilization is the fraction of time the server is busy:

$$\rho = \lambda \cdot E[S]$$

• $\rho = 0.5$: the server is busy half the time.
• $\rho = 0.95$: the server is busy 95% of the time.
• $\rho \geq 1$: requests arrive faster than they can be processed. The queue grows forever (unless something drops requests or adds capacity).

Stability condition: for a queue to have a finite average wait time, you need $\rho < 1$.

---

Queue depth (queue length)

The number of requests currently waiting to be processed, excluding the one currently being served. In the event loop, this is the backlog of callbacks sitting in the loop while one callback is executing.

When $\rho$ creeps close to 1, queue depth becomes very sensitive to small changes in load.

---

Second moment of service time ($E[S^2]$)

The average of the squared service times. It captures both the mean and the variance of the distribution:

$$E[S^2] = \text{Var}(S) + (E[S])^2$$

Why it matters: the Pollaczek–Khinchine formula shows that average waiting time in an M/G/1 queue depends on $E[S^2]$, not just $E[S]$. A heavy tail (high variance) dramatically increases waiting time even when the mean service time stays the same.

---

Quick recap table

Term	Symbol	Plain English
Arrival rate	$\lambda$	How fast requests come in
Mean service time	$E[S]$	How long it takes to handle one request
Utilization	$\rho$	How busy the server is
Second moment	$E[S^2]$	How "spread out" service times are (mean + variance)
Queue depth	—	How many requests are waiting
Stability	$\rho < 1$	The system can keep up with arrivals

---

Further reading

• Kendall's notation
• M/G/1 queue
• Pollaczek–Khinchine formula