The Locality and Load Balancing Tradeoff

26 concepts26 papers1 proposal

In distributed computing, two forces constantly pull in opposite directions: data locality and load balancing. Data locality suggests that we should process data where it lives to avoid the high cost of moving it across a network. Load balancing suggests we should spread work evenly across all available processors to ensure no single node becomes a bottleneck.

As William Gropp noted in early computational fluid dynamics research, this conflict is fundamental. If you prioritize locality, you risk "hotspots" where a few nodes are overwhelmed while others sit idle. If you prioritize load balancing, you risk "network exhaustion" where the time gained by parallel processing is lost to the overhead of moving data.

The Locality Trap: When Proximity Creates Bottlenecks

The intuitive goal of a distributed system is to minimize communication. In database systems, Yu et al. observed that routing requests to the node where the data is already cached (locality) is the most efficient path—until that node reaches capacity. Once a node is saturated, the "locality benefit" vanishes, replaced by queuing delays.

This problem is particularly acute in modern Large Language Model (LLM) serving. Systems often use "prefix caching" to store the intermediate states of long prompts (like a massive codebase or a textbook). Srivatsa et al. explain that while routing all queries about a specific document to one GPU maximizes cache reuse, it creates severe processing bottlenecks if that document becomes popular. Similarly, in edge computing, Tang et al. found that placing containers on nodes that already have the required image layers (locality) can lead to resource hotspots, leaving nearby nodes underutilized.

The Load Balancing Tax: The Cost of Spreading Out

The alternative—distributing work perfectly across the cluster—comes with its own "tax." In sharded blockchains, Li et al. show that aggressive load balancing increases the frequency of expensive cross-shard transactions. In these scenarios, the system spends more time coordinating between nodes than actually processing data.

Even in high-performance linear algebra, the tradeoff persists. Buluc et al. point out that techniques used to fix load imbalances, such as random data permutation, often destroy spatial locality, which in turn degrades local cache performance and increases the volume of data movement. Santos et al. further demonstrate that "spreading" AI workloads across multiple racks to gain aggregate throughput can backfire by increasing network hop counts and oversubscribing leaf switches.

Finding the Equilibrium

Modern research focuses on breaking this zero-sum game through adaptive and predictive strategies. Rather than choosing one extreme, researchers are developing mechanisms to navigate the "sweet spot" between the two:

  • The Power of Two Choices: Instead of routing a task to the single best node for locality, Yuan et al. propose mapping requests to two candidate nodes. This "DualMap" approach maintains high cache hit rates while allowing the system to steer traffic away from whichever of the two nodes is more congested.
  • Predictive Routing: Huang et al. demonstrate that using short-term traffic predictions allows a scheduler to proactively move data or tasks, maintaining queue stability without sacrificing locality.
  • Topology-Aware Placement: For complex models like Mixture-of-Experts (MoE), Katrutsa et al. use integer linear programming to place "experts" in a way that respects the physical network topology, reducing communication hops while preventing memory bottlenecks.
  • Sacrificing Locality Early: In MapReduce frameworks, Wu et al. found that intentionally sacrificing some locality during the initial "Map" phase can prevent massive network congestion during the subsequent "Shuffle" phase, leading to faster overall job completion.

Ultimately, as Sun et al. argue in the context of graph processing, achieving a global load balance is often more critical for performance than enforcing strict data locality. The most effective systems are those that treat locality not as a rule, but as a resource to be traded when the cost of imbalance becomes too high.

Key Foundational Work

Robust Transaction-Routing Strategies in Distributed Database Systems (1989) — contributed 1 concept elements to this direction.
Domain decomposition methods in computational fluid dynamics (1992) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_locality_load_balancing_tradeoff_ba7b0db7,
  title = {locality-load balancing tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/locality-load-balancing-tradeoff/rdr_ba7b0db79152464ca107a41e078ad447},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_locality_load_balancing_tradeoff_ba7b0db7_v1,
  title = {locality-load balancing tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/locality-load-balancing-tradeoff/rdr_ba7b0db79152464ca107a41e078ad447/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake