Investigation 034 · Distributed Systems Economics

The Bin Packing
Problem

“A placement can be correct and still make the next correct placement impossible.”

How to Read This Investigation

Correct is not the same as economically wise.

INV-014 established that filtering and ranking are different responsibilities. Filtering determines which destinations are acceptable. Ranking chooses among destinations that have already passed that correctness boundary. INV-034 enters precisely there.

We will not ask how to make an infeasible destination feasible, and we will not assume that tighter packing is inherently better. We will ask a narrower question: when several destinations are all correct, what makes one preferable to another?

What must an economic comparison be honest about before a policy is allowed to call one correct placement better than another?
An unresolved input. The comparison receives a value called available capacity. Later failures must determine what that value means and what claims it can support.
The Mystery

Three correct answers. Three different futures.

A workload needs both processor capacity and memory. Three machines can satisfy it. Machine A has plenty of processor capacity remaining but little memory. Machine B has plenty of memory but little processor capacity. Machine C has moderate amounts of both. The workload can run on all three.

Foundation

INV-014 already established that filtering and ranking are separate responsibilities, and INV-019 already established that processor and memory are finite, explicitly owned resources.

Assumption

If a destination is feasible, choosing any one of them should be just as good as choosing another.

Incident

Placing the workload on Machine A leaves one shape of remaining capacity. Placing it on Machine B leaves another. The workload is satisfied either way, but the cluster is not left in the same condition.

Machine Aprocessor-heavy remainder
Machine Bmemory-heavy remainder
Machine Cmoderate remainder
Mystery: how can the platform compare economically different, individually correct placements when capacity has shape, observations arrive late, decisions happen concurrently, and future demand is unknown?
First Principles

Feasible does not mean equivalent.

The placement system has already rejected every destination that cannot satisfy the workload. What remains is a set of destinations that are all correct. Multiple resources alone do not create an architectural problem — the problem appears only when the consequences of choosing one feasible destination differ materially from choosing another.

Correctness

Answers whether a destination can run the workload at all.

Preference

Answers which correct destination the platform would rather use, according to some objective.

Consequence

The same choice can be economically irrelevant in one cluster and materially important in another — abundance hides the difference; scarcity reveals it.

Deferred question: is more sophistication always better? Not automatically. A system should earn complexity — introducing comparison before consequences differ enough to justify it would be architecture nobody needed. That is not yet established here.
The Smallest Design

Choose any feasible destination.

First, determine which destinations are feasible. Then choose one. There is no scoring stage, no economic model, no attempt to understand the future — simply a selection from the set of correct answers.

Workloadneeds processor + memory
Feasibility FilteringA ✓ · B ✓ · C ✓
Choose Anyno scoring, no prediction

Why it works

No additional information, no future-demand model, no scoring function — it does not pretend to know more than it actually knows.

Abundant capacity

Similar machines, similar workloads, abundant spare capacity, low placement volume — the choice among feasible destinations may have very little economic consequence.

The untested assumption

Consequences differ only when residual capacity shapes diverge enough to matter — this design has not yet been tested against that condition.

The Architecture That Almost Worked

Score each destination. Choose the highest.

Give processor and memory equal influence: average the remaining share of each. Machine A retains 4 of 8 processor and 4 of 16 memory — a score of 0.375. Machine B retains 2 of 8 processor and 4 of 16 memory — a score of 0.250. Machine A is preferred.

Machine Ascore 0.375
Machine Bscore 0.250
PreferredMachine A

What it preserves

The correctness boundary. A less-preferred destination remains feasible; the objective is explicit and replaceable rather than hidden inside selection.

What it assumes

One ordering is enough. Averaging processor and memory shares into a single number is assumed to preserve everything a later decision might need to know.

The score treats every resource dimension as interchangeable. What does that arithmetic quietly throw away?
Breaking Our Design

Run each pressure in causal order.

Episode 01 begins from the almost-worked score. Each later experiment unlocks only when the preceding discovery creates its reason to exist. Every experiment remains independently resettable.

EPISODE 01

Capacity Has Shape

Can one scalar preserve the combinations that future workloads require?

Machine A10 proc / 2 mem
Machine B5 proc / 7 mem
ScoreNot compared

Apply the averaging formula to both residual shapes.

EPISODE 02

Tomorrow's Workload Is Unknown

What can a preference claim before the demand it hopes to serve exists?

ObjectiveNot chosen
Future AUntested
Future BUntested

Choose an explicit objective before testing alternate futures.

EPISODE 03

Capacity Accounting Is Not Physical Reality

Which meaning of capacity supports the comparison?

Physical useNot observed
AccountedNot observed
New commitmentUnknown

Observe physical use and accounted commitments separately.

EPISODE 04

Two Good Decisions Collide

What must hold when separate records consume one shared capacity account?

Capacity account8 proc / 16 mem
Worker ANot evaluated
Worker BNot evaluated

Let both workers read the same capacity account.

Review the four experiments
    The Turning Point

    Stop asking which score is highest.
    Ask what the comparison is honest about.

    The four failures did not describe four unrelated bugs. They exposed the conditions an economic comparison must preserve: resource dimensions that survive comparison, a bounded claim about the future, a capacity value that keeps the meaning of its accounting model, and commitments that stay compatible across independent records.

    Feasible Destinationsalready correct
    Bounded Preferenceexplicit objective · modeled capacity
    Recorded Placementcompatible commitment
    The Economic Comparison Contract

    Correctness first. Preference second. Both honest.

    Filtering still says which choices are allowed. Comparison says which allowed choice the current policy prefers. Neither responsibility may silently borrow the other's authority. Ten obligations hold that boundary together.

    Responsibility 1 — Explicit objective

    A comparison must not present an undefined notion of “better” as though it were a correctness property.

    Responsibility 2 — Multidimensional capacity

    Comparison must preserve the resource dimensions relevant to the capacity model rather than collapsing them into one scalar.

    Responsibility 3 — Bounded by information

    A preference may claim only what the available capacity information and accounting state support — never a guaranteed future outcome.

    Responsibility 4 — Future demand not known

    No economic ranking may honestly guarantee an outcome for demand that has not yet occurred.

    Responsibility 5 — Defined capacity meaning

    Physical consumption, reported state, accounted commitments, schedulable capacity, and preference remain distinguishable concepts.

    Responsibility 6 — Preserve declared semantics

    A commitment must remain compatible with the capacity semantics the platform declared for that account, not an assumed universal no-overcommitment rule.

    Responsibility 7 — Observation is not ownership

    Observing capacity does not reserve it — the world may change before that observation is used.

    Responsibility 8 — Shared-capacity compatibility

    Commitments from different workload records must not silently become authoritative when their combined assumptions are incompatible under the declared capacity model.

    Responsibility 9 — No universal objective

    Tighter packing, spreading, balance, and fragmentation reduction remain explicit, replaceable policy choices rather than architectural truth.

    Responsibility 10 — No mechanism chosen

    The contract requires compatibility across shared commitments without selecting the mechanism that realizes it.

    Architecture, not policy. The contract requires an explicit, replaceable objective and honest information boundaries. A scoring formula, resource weights, and utilization targets remain policy or mechanism.

    Correctness, preference, and shared capacity remain three separate things. The architecture must never let one silently stand in for another.

    Only Now: Kubernetes

    The scheduler realizes filter-then-score.

    The kube-scheduler filters nodes for feasibility, then scores the surviving nodes through replaceable scoring plugins — the Scheduler Framework's Filter and Score extension points. NodeResourcesFit can be configured with a MostAllocated or LeastAllocated strategy, making the objective this investigation calls policy an explicit, swappable configuration rather than a hidden constant.

    Filterfeasible nodes only
    Scorereplaceable scoring plugins
    Bindone recorded placement

    Requests, not usage

    Pod resource requests are compared against node allocatable capacity — a modeled account, not live physical utilization.

    Replaceable policy

    Scheduler Framework scoring plugins express ranking policy after filtering rather than redefining feasibility.

    Unresolved realization

    The shared-capacity compatibility invariant does not select a reservation, transaction, cache, lock, or serialization mechanism.

    A scoring plugin is narrower than an optimizer. It ranks already-feasible nodes under one configured, replaceable objective. It does not predict future workloads, guarantee optimal packing, or resolve what happens when independent scheduling decisions rely on the same assumed capacity — those remain the boundaries this investigation derived, not settled by the plugin's existence.
    A preference is a claim about
    what is known, not what will happen.

    Keep the simplest choice

    • Machines and workloads are similar
    • Spare capacity is abundant
    • Placement volume is low
    • Fragmentation is not a concern yet

    Introduce economic comparison

    • Residual capacity shapes diverge materially
    • Placement choices recur at scale
    • An explicit, replaceable objective is worth its cost
    • Shared commitments need compatibility protection
    Architectural Honesty

    A richer economic comparison is not automatically the better design. It requires more information, more computation, more policy to maintain, and sometimes more coordination when independent decisions rely on shared capacity. In a small cluster with abundant spare capacity, a simple stable rule may leave enough room for almost everything that arrives — 100 machines with 8 processor and 32 memory units each holding 2 and 8 units free per machine still total 200 processor and 800 memory units free, yet a workload needing 4 processor and 16 memory may fit nowhere if that residual capacity is scattered rather than concentrated.

    Costs Accepted

    Information cost

    Better comparison requires more frequent, more detailed capacity reports — 10,000 machines reporting every second instead of every 10 seconds is a 10x increase in observation traffic.

    Objective cost

    Every additional preference invites the question “why this preference,” and must remain explicit and replaceable rather than hidden inside a score.

    Shared-commitment cost

    Protecting compatibility across independent records is not free, but neither is allowing incompatible assumptions to become authoritative.

    These costs are accepted only when the arrangement of capacity — not merely its aggregate total — materially affects what the platform can accept next.

    Investigation Exercise

    Equal scores. Different futures.

    Machine A holds 10 processor / 2 memory. Machine B holds 5 processor / 7 memory. Machine C holds 2 processor / 10 memory. Predict which machine a scalar processor + memory score prefers, then test that preference against three different future workloads.

    Prediction

    Which machine does a scalar score prefer, and does that ranking hold for every possible future workload?

    Experiment

    Check three future workloads — processor-heavy, balanced, memory-heavy — against the same three machines without changing the score.

    Observation

    Equal or similar aggregate capacity does not imply equal usefulness — capacity has shape.

    Reflection

    Was the original decision wrong, or was it a preference bounded by the objective and information available at the time?

    ● ● ●
    Earn the comparison contract to unlock this trace.
    The Comparison Is Bounded

    The placement was reasonable when made.
    Capacity does not stay still.

    Correctness was established before preference.

    The objective was explicit, and capacity kept the meaning of its accounting model.

    Independent commitments still had to preserve the declared compatibility semantics of their shared capacity account.

    New demand evidence can still make that recorded assumption look wrong.

    Feasible destinations pass through an explicit economic comparison that preserves capacity shape, a bounded future claim, and compatible shared commitments, ending in one recorded placement, before new demand evidence exposes the unresolved elasticity problem
    What, if anything, should happen when new demand evidence no longer appears consistent with an existing capacity commitment?

    Intellectual Lineage

    This investigation inherits the placement contract from INV-014, finite-resource ownership from INV-019, and the authoritative admission transition from INV-033. Separating correctness from economic preference under uncertainty is a long-standing pattern in distributed scheduling: cluster schedulers such as Omega reason over shared, optimistically-concurrent cluster state rather than a single global arbiter. Kubernetes’ filter-then-score scheduler is one realization of the broader Economic Comparison Contract derived here; this investigation does not claim that any particular scoring strategy is universally correct.

    Deliberate Simplifications Ledger

    How shared-capacity compatibility is realized (reservations, transactions, or another mechanism)Mechanism design — unassigned
    How changed demand evidence may lead toward a revised capacity commitmentINV-035
    How insufficient capacity is divided among independently owned workloadsINV-036
    When committed capacity may be reclaimed, and the availability boundary on displacementINV-037, INV-038
    How repeated placement and recovery work stays economically boundedINV-039

    Sources