Queues, Bursts, and Locality Create Dependence

By the end of this lesson, you will be able to...

• Build a small queue simulation with arrivals, service capacity, and routing.

• Predict how bursts and locality create correlated waiting times even when global averages look safe.

• Change one parameter, inspect the emergent behavior, and name what the model leaves out.

Idea in one sentence: Dependence becomes operationally visible when work arrives in bursts or concentrates on one resource instead of spreading independently across the system.

Core Insight

Consider an image-processing service with two workers. Each worker can finish two jobs per minute. The global dashboard reports an average of three jobs per minute, so the team expects spare capacity: total capacity is four.

The dashboard does not show where the jobs go. A popular customer may upload many images with the same routing key, sending them all to one worker. A burst can then fill one queue while the other worker is idle. The next job’s waiting time depends on the queue left by earlier jobs. The system has acquired memory through accumulated work.

This lesson turns that mechanism into a small simulation. The goal is not to predict one production queue exactly. It is to see how local rules create a global pattern that an average-rate calculation cannot reveal.

The Phenomenon

There are three sources of dependence to keep separate:

1. Bursts: arrivals cluster in time instead of appearing evenly.
2. Locality: related jobs choose the same worker, shard, cache, or region.
3. Finite service: a resource can process only a limited number of jobs per step.

Each source changes the next state. If a queue is already long, a new job waits longer. If a hot key keeps choosing one shard, that shard remains under pressure. If the arrival mode switches from quiet to bursty, several future observations may share the same hidden regime.

The global arrival rate still matters, but it is only one parameter. We also need the distribution of arrivals over time and resources.

The Model Pieces

Use two workers \(j\in\{0,1\}\), each with service capacity \(c_j=2\) jobs per time step.

• \(A_t\): jobs arriving during step \(t\).
• \(K_i\): routing key of job \(i\), such as tenant or object id.
• \(h(K_i)\): worker selected by the routing function.
• \(Q_j(t)\): queue length for worker \(j\) after service at step \(t\).
• \(W_i\): waiting time experienced by job \(i\).

The model has two routing modes:

• Uniform: each job chooses either worker with probability \(1/2\).
• Local: a hot key sends repeated jobs to the same worker; other jobs may still be uniform.

For arrivals, compare:

• Smooth: a nearly fixed number per step.
• Bursty: a quiet or active mode persists for several steps.

The simulation keeps the rule simple enough to inspect. Every difference in behavior should be traceable to a changed parameter or rule.

The Rules

At each time step:

1. Sample the number and keys of new jobs.
2. Route each job to a worker and append it to that worker’s queue.
3. Let each worker process at most \(c_j\) jobs.
4. Record queue lengths, completions, and waiting times.

For one worker, the queue update is:

where \(A_j(t)\) is the number of jobs routed to worker \(j\) at step \(t\). The global arrival rate is:

The local load is different:

Even when \(\lambda<\sum_j c_j\), one worker can have \(\lambda_j>c_j\) for long enough to create a persistent queue.

For a simple burst mode, let \(M_t\) be either quiet or active. The mode persists with probability \(p\):

An active mode emits more arrivals than a quiet mode. This reuses the hidden-state intuition from lesson 013: the mode is a compact cause of temporal dependence.

One Step at a Time

Start with empty queues and capacity \(c_0=c_1=2\). Let key \(A\) always route to worker 0 and key \(B\) to worker 1.

Eleven jobs arrive over four steps, an average of 2.75 per step, below total capacity \(4\). Nevertheless, worker 0 ends with a queue of two. A global average says “capacity is sufficient”; the local trace says “one routing class is accumulating work.”

Now route the same total number of jobs uniformly. If each step sends roughly half to each worker, neither queue reaches the same peak. The total work did not change. The allocation rule did.

Waiting time is now dependent. A job arriving at worker 0 in step 4 inherits the two jobs left by earlier arrivals. Its waiting time is not drawn independently from the same distribution as the first job in step 1. The queue is the state that carries the past forward.

A Minimal Simulation

The following pseudocode is enough to run the experiment in any language:

queues = [0, 0]
mode = quiet
for t in 1..T:
    mode = maybe_switch(mode, persistence)
    jobs = sample_arrivals(mode, mean, burst_size)
    for job in jobs:
        worker = route(job.key, locality)
        queues[worker] += 1
    for worker in [0, 1]:
        served = min(queues[worker], capacity[worker])
        queues[worker] -= served
        record(queue=queues[worker], served=served)

Run several independent seeds. A single run illustrates one path; repeated runs show the distribution of maximum queue, mean waiting time, and fraction of jobs delayed.

What Changes When We Change a Parameter

Increase burst persistence

When the active mode persists longer, active steps arrive in runs. The global mean may stay fixed over a long simulation, but queue maxima and tail waiting times grow. Nearby observations become more correlated.

Increase locality

When the probability of reusing the hot key rises, jobs concentrate on one worker. The other worker can be idle while the hot queue grows. Adding total capacity without changing routing may not help the overloaded shard.

Increase service capacity

Increasing \(c_j\) drains queues faster, but it may not eliminate tail delays if bursts exceed capacity for several consecutive steps. Capacity should be compared with short-window peaks, not only the long-run mean.

Change the time step

A one-minute simulation can hide sub-second bursts. A smaller step reveals sharper peaks but creates more random variation and more data to interpret. The resolution should match the mechanism that drives the decision.

Replace locality with work stealing

Allowing an idle worker to take work from a hot queue can reduce imbalance. It may add coordination cost, cache misses, or ordering constraints. The simulation can expose this trade-off without claiming that one policy is universally best.

What Emerges

The model can produce several patterns that were not explicitly inserted as a single formula:

• Queue buildup: a run of arrivals exceeds local service capacity.
• Hysteresis: after the burst ends, the queue remains high while it drains.
• Correlated latency: jobs arriving during the same episode share queue pressure.
• Shard imbalance: locality creates one hot worker and one underused worker.
• Tail amplification: a modest change in burst size can create a large change in maximum waiting time.

These are emergent because they result from repeated local rules. No job “knows” about the global queue, yet the system develops a long-lived state that affects later jobs.

The simulation also makes a statistical warning concrete. If we sample only quiet periods, we underestimate waiting-time tails. If we average across workers, we hide locality. If we report only the mean, we miss the queue’s memory.

What The Model Leaves Out

This model is deliberately small:

• Service times are fixed rather than variable.
• Workers do not fail or recover.
• Routing keys are known and stable.
• Jobs do not cancel, retry, or change priority.
• The active/quiet mode is only an approximation of real demand.
• The queue discipline is first-in, first-out.

Those omissions matter. Variable service times can create queues even with smooth arrivals. Retries can amplify a burst. A failed worker can turn a balanced system into a hot shard. The model is useful only when its simplifications are stated next to its conclusions.

Common Confusions

Confusion: Average arrival rate below capacity guarantees no queue

Better model: capacity must cover local and short-window demand. Bursts and locality can exceed a worker’s capacity while the global average remains safe.

Confusion: Dependence requires a complicated formula

Better model: a queue is already a state variable. The next waiting time depends on the work left by prior jobs.

Confusion: Random simulation proves the production system behaves that way

Better model: simulation tests consequences of explicit rules. It supports a claim only when those rules are plausible and the observed pattern is compared with real data.

Confusion: More workers always solve locality

Better model: additional workers help only if work can reach them. A hot key pinned to one shard can remain a bottleneck.

Experiment: Change One Rule

Implement the two-worker simulation for \(T=1{,}000\) steps. Start with capacity 2 per worker, mean global arrivals of 3 per step, and record maximum queue length, mean waiting time, and the 95th percentile waiting time.

Run these four conditions:

1. Smooth arrivals, uniform routing.
2. Bursty arrivals with mode persistence \(p=0.8\), uniform routing.
3. Smooth arrivals, locality that sends 80% of jobs to one hot key.
4. Bursty arrivals and the same locality.

Keep the random seed list fixed across conditions. Predict before running:

• Which condition has the largest maximum queue?
• Which condition produces the biggest gap between mean and p95 waiting time?
• Does the global arrival rate change, or only its temporal and local arrangement?
• What happens if capacity rises from 2 to 3 on the hot worker?

Expected interpretation

Conditions 2 and 3 should produce more dependence than condition 1 for different reasons: bursts cluster jobs in time, while locality clusters them on a resource. Condition 4 combines both pressures and should usually have the heaviest tail. Exact values vary by seed, so report a distribution across runs rather than one lucky result.

If capacity rises only on the non-hot worker, little changes. If the hot worker gains capacity or work stealing is enabled, the tail may shrink, but coordination and resource costs should be recorded as part of the decision.

Connections

Lesson 012 introduced bursts and autocorrelation as time-series patterns. Lesson 013 showed how a hidden mode can persist. This lab turns both ideas into queue state, local routing, and measurable waiting-time tails. Lesson 015 will use these mechanisms in a cross-track audit, and lesson 016 will ask for a complete diagnosis of a noisy system.

Resources

• [COURSE] MIT OpenCourseWare: Introduction to Probability - Focus: Connect repeated random trials and conditional behavior to simulation design.
• [REFERENCE] NIST/SEMATECH e-Handbook: Queueing - Focus: Compare simple queueing summaries with simulation-based reasoning and capacity assumptions.

Key Takeaways

• A queue is a memory variable: unfinished work makes future waiting times dependent on the past.
• Bursts concentrate demand in time; locality concentrates demand on a resource.
• Global averages can look safe while local queues and tail latency become dangerous.
• A simulation is a controlled argument about explicit rules, not a replacement for production evidence.
• Change one parameter at a time, repeat across seeds, and report the emergent distribution together with the model’s limits.