Adaptive Sampled Marginal Feedback (ASMF) Load Balancer

TL;DR

ASMF is a distributed load-balancing algorithm that trades a small amount of latency optimality for a large reduction in coordination overhead. In the current experiments it achieves:

about 80-90% lower query overhead than global-state methods such as gmsr and least_queue
competitive throughput with p2c
improved backlog and wait time over the baseline ASMF configuration after tuning
stable behavior across independent seed blocks after parameter refinement

ASMF is a hybrid distributed load-balancing algorithm designed for scalable and adaptive routing under partial system information.

This repository documents a full research workflow, not only an implementation. The algorithm was validated incrementally through smoke tests, full benchmarks, rigorous multi-scenario studies, parameter tuning, and a final robustness comparison on a disjoint seed block. The outputs/ folder preserves this evidence trail so the final claims can be reproduced and checked.

This work demonstrates that carefully tuned, feedback-driven sampled routing can approach full-information performance in some regimes while significantly reducing coordination cost in distributed systems.

Project Description

The goal is to route requests to backends in a distributed system without requiring perfectly fresh global state. ASMF combines sampled candidate selection, a marginal score, a feedback correction term, and multi-resource load awareness so it can remain practical under partial information while still reacting to overload and resource imbalance.

It combines:

GMSR-style marginal scoring
power-of-k sampling
DFLB-inspired feedback correction
multi-resource load awareness
low-overhead state sharing

Core Idea

For backend $j$, ASMF computes:

$$ L_j = \alpha CPU_j + \beta MEM_j + \gamma IO_j + \delta NET_j $$

$$ S_j = \frac{\mu_j}{(1 + q_j)(1 + L_j)} $$

Feedback update:

$$ \Delta_j = \lambda^{in}_j - \lambda^{svc}_j $$

$$ C_j(t+1) = \mathrm{clip}\left(C_j(t) - \eta \Delta_j, C_{min}, C_{max}\right) $$

Final score used for routing:

$$ S'_j = S_j \cdot C_j $$

Routing rule:

sample $k$ allowed backends
choose backend with maximum cached $S'_j$
reject/delay if $\max S'_j < \tau$

Equation Interpretation

$(1 + q_j)$ penalizes queue buildup and acts as a delay-pressure term.
$(1 + L_j)$ penalizes multi-resource saturation.
The multiplicative denominator ensures a backend highly loaded in either queueing or resources is deprioritized.

This form is a practical approximation to marginal service utility under joint queueing and resource constraints, while still being computable from partial local state.

Feedback Stability Intuition

The update

$$ C_j(t+1) = C_j(t) - \eta\Delta_j $$

acts as a discrete-time control loop on load imbalance:

if $\lambda^{in}_j > \lambda^{svc}_j$, then $\Delta_j > 0$, so $C_j$ decreases and the backend is less preferred
if $\lambda^{in}_j < \lambda^{svc}_j$, then $\Delta_j < 0$, so $C_j$ increases and the backend becomes more preferred

For sufficiently small $\eta$, this behaves as a damped correction process. Clipping to $[C_{min}, C_{max}]$ bounds transients and prevents runaway oscillation.

Complexity Justification

Each decision evaluates only $k$ sampled backends, so per-request routing computation is $O(k)$ and sampled-state query cost is also $O(k)$. Global-state policies that inspect all backends scale as $O(n)$ per decision.

Mechanism and Basis

ASMF is based on four ideas:

Sampled routing: instead of scanning every backend, ASMF evaluates a small candidate set. This keeps routing cost low and gives an $O(k)$-style decision cost per request.
Marginal scoring: the score combines queue pressure and resource load, so routing is not driven by queue length alone.
Feedback correction: the correction term is updated from inflow minus service completion. This makes the policy adaptive to sustained overload drift instead of static.
Multi-resource awareness: CPU, memory, IO, and network are folded into the score so hidden bottlenecks are not ignored.

This design explains the research basis of ASMF: it is a practical distributed routing policy for partial-state environments, not a global-oracle algorithm. The experiments show that the sampled and feedback-driven design is what allows ASMF to behave well under stress while keeping coordination overhead bounded.

The tuned experiments identified asmf_tuned_v2 as the strongest balanced ASMF variant. The tuning runs point to a stable parameter band rather than a single fragile setting.

Mathematical and Empirical Foundations

Theoretical Interpretation

ASMF can be understood as a distributed approximation of marginal utility maximization in a stochastic queueing system. It combines three classical ideas:

1. Marginal Service Efficiency (Queueing Theory)

The base score:

$$ S_j = \frac{\mu_j}{(1 + q_j)(1 + L_j)} $$

acts as a proxy for marginal service contribution. Decomposed:

$\mu_j$ represents backend $j$'s service rate (throughput capacity)
$(1 + q_j)^{-1}$ penalizes queue buildup (approximates delay increase in $M/M/1$ systems where delay $\propto \frac{1}{1 - \rho}$)
$(1 + L_j)^{-1}$ penalizes multi-resource saturation (extends queue-only models to include CPU, memory, IO constraints)

This structure reflects the intuition behind policies like GMSR: routing decisions should favor backends with the highest remaining service capacity relative to current load.

2. Feedback as Drift Correction (Stochastic Control)

The feedback update:

$$ C_j(t+1) = C_j(t) - \eta \Delta_j, \quad \Delta_j = \lambda^{in}_j - \lambda^{svc}_j $$

acts as a discrete-time control loop for load imbalance. This is analogous to:

Gradient descent on load imbalance: $\Delta_j$ measures instantaneous mismatch between arrival and service; negative $\eta$ corrects toward balance
Lyapunov drift stabilization: clipping to $[C_{min}, C_{max}]$ bounds the drift and ensures bounded system behavior even under sustained overload
Adaptive feedback control: small $\eta$ provides damped correction (avoiding oscillation), while larger values risk instability

3. Sampled Approximation (Distributed Systems)

Instead of solving the global optimization:

$$ j^* = \arg\max_j S'_j $$

ASMF approximates via:

Random sample $k$ backends uniformly
Select $j^* = \arg\max_{j \in \text{sample}} S'_j$

This trades optimality for scalability:

Time complexity: $O(k)$ per decision (vs $O(n)$ for full scan)
Communication complexity: $O(k)$ state queries per request (vs $O(n)$ for policies like least_queue or GMSR)
Approximation quality: follows power-of-k analysis (sampling $k$ random items from $n$ gives nearly-optimal selection with high probability)

Empirical Evaluation Scope

The algorithm was rigorously evaluated across:

Evaluation Matrix

8 scenarios: poisson/bursty/zipf_skew workloads (3) × small/medium/large scales (3) + stress events (2: failure, spike)
8 policies: ASMF (default + 3 tuned variants) + 4 ablations (no_feedback, no_sampling, no_multiresource) + 4 baselines (GMSR, P2C, least_queue, random)
Independent repetitions: 20 seeds per scenario in rigorous study; 20 seeds × 2 disjoint blocks (101:120, 121:140) in final comparison
Total runs: 1,280 runs (rigorous) + 1,280 (final comparison) + 1,280 (robustness) = 3,840 simulator runs
Metrics: throughput, average wait, backlog area, queries per decision, convergence time, queue variance, oscillation index

Key Empirical Findings With Evidence

ASMF vs. Random Baseline

Throughput improvement: +4–5%
Wait time reduction: ~45%
Backlog area reduction: ~40%
Status: Consistent and strong across all scenarios

ASMF vs. P2C (Both Sampled Policies)

Throughput: near identical (within 0.1%)
Wait time: mixed; ASMF competitive in small scale, P2C leads slightly at medium/large
Status: ASMF achieves comparable performance to a well-known sampled baseline while using multi-resource scoring

ASMF vs. GMSR and Least Queue (Global-State Policies)

Throughput: slightly lower (−0.1% to −0.4% depending on scenario)
Wait time: varies by scenario; GMSR leads in high-stress conditions
Backlog: ASMF competitive at small scale; global-state methods lead at medium/large
Status: Expected performance tradeoff; ASMF lacks global information but maintains scalability

Communication Efficiency (Core Contribution)

ASMF: ~3 queries per decision (sample of $k=3$ backends)
GMSR: ~40+ queries per decision (full state check)
Least Queue: ~50+ queries per decision (checking all backends)
Reduction: ASMF uses 80–90% fewer state queries than global-state methods

Ablation Results (Design Validation)

asmf_no_sampling (use all backends instead of sample): communication cost increases 10–15×, latency degrades sharply → confirms sampling is essential
asmf_no_feedback (remove correction term): throughput stable, wait time increases 3–8% → confirms feedback is beneficial but tuning-sensitive
asmf_no_multiresource (queue-only scoring): mixed results across scenarios, worse at medium/large scales → confirms multi-resource awareness is important but requires calibration

Robustness Across Disjoint Seed Blocks (n=320 Paired Comparisons)

The tuned variant asmf_tuned_v2 was evaluated on two independent seed blocks:

Seeds 101:120 (final_comparison): baseline reference
Seeds 121:140 (final_comparison_robust): unseen, independent validation

Results showed:

Throughput improvement vs. baseline: +0.19% (consistent across blocks)
Wait time reduction: −4.7% (stable)
Backlog reduction: −4.3% (stable)
Ranking of policies remained consistent between blocks
Status: Improvements are not seed-specific; the tuned configuration generalizes

What This Achieves

Collectively, these results establish ASMF as:

A distributed, low-overhead approximation of marginal service rate routing with adaptive drift correction.

Specific contributions:

Theoretical grounding: combines queueing theory (marginal service), control theory (drift correction), and distributed systems (sampling approximation)
Empirical validation: ablations isolate each component; comparisons with multiple baselines show practical positioning
Robustness: improvements validated on independent seed blocks; stable parameter region identified
Scalability: 80–90% reduction in coordination cost while maintaining competitive throughput

This frames ASMF as a principled, theoretically motivated algorithm validated across diverse stochastic workloads and scales.

Key Empirical Findings

ASMF reduces query overhead by roughly 80-90% compared with global-state policies such as gmsr and least_queue.
Tuned ASMF variants consistently outperform the baseline ASMF configuration across independent seed blocks.
ASMF achieves competitive throughput relative to p2c while improving backlog in several regimes.
Performance is scenario-sensitive: the strongest gains appear at small scale, while global-state methods retain advantages in some medium-scale regimes.
asmf_no_sampling degrades sharply, confirming that candidate sampling is essential for scalability.

Empirical Validation of Design Choices

Sampling design: asmf_no_sampling substantially increases overhead and degrades delay behavior in multiple scenarios, validating sampling as a scalability mechanism.
Feedback design: differences between asmf and asmf_no_feedback indicate that feedback is useful but tuning-sensitive; overly aggressive updates can hurt stability.
Multi-resource design: asmf_no_multiresource shows mixed behavior across scenarios, confirming that resource-awareness is important but weight calibration is critical.
Partial-information design: tuned ASMF variants maintain competitive throughput in several regimes while using much lower coordination overhead than global-state methods.

Recommended operating band from the tuned runs:

sample_k: 2 to 4, centered near 3
eta: about 0.006 to 0.019
threshold: about 0.109 to 0.139
min_correction: about 0.712 to 0.865
max_correction: about 1.306 to 1.626

Research Process Used Here

The research was executed in stages so each step could be validated before moving forward:

Build and smoke-test the policy logic in a short simulation.
Run the benchmark suite and verify the policy/baseline paths.
Expand to multiple workloads, system sizes, and stress events.
Add ablations to isolate sampling, feedback correction, and multi-resource scoring.
Run tuning sweeps to narrow the best parameter region.
Re-run the full comparison with tuned variants.
Repeat the final comparison on a disjoint seed block to confirm robustness.

The main evidence folders are:

outputs/rigorous/: full ablation and statistical study
outputs/tuning_speedcheck_w6/: tuning evidence and top variants
outputs/final_comparison/: main tuned-vs-baseline comparison
outputs/final_comparison_robust/: robustness comparison on a second seed block

Repository Layout

src/asmf_lb/engine.py: ASMF policy and baselines
src/asmf_lb/simulator.py: discrete-event simulation and topology generation
src/asmf_lb/experiments.py: benchmark suite, summary generation, and plots
scripts/run_experiments.py: full benchmark run
scripts/quick_demo.py: short local demonstration
tests/test_engine.py: routing and feedback unit tests
docs/PROOF_SIMULATIONS.md: simulation proof protocol
docs/GITHUB_PUBLISH_PROTOCOL.md: GitHub submission workflow

Execution Workflow

Use this order if you want to reproduce the full research path from a fresh checkout.

1. Create and install the environment

python -m venv .venv
.venv\Scripts\activate
pip install -r requirements.txt
pip install -e .

2. Run a quick demo

python scripts/quick_demo.py

This is the fastest way to verify that the package imports, the policy wiring works, and the simulator can run end to end.

3. Run the baseline benchmark layer

python scripts/run_experiments.py

This is a smaller benchmark pass and is useful as a light sanity check before the full campaign.

4. Run the rigorous campaign

python scripts/run_rigorous_testing.py
python scripts/analyze_rigorous_results.py

This produces the main empirical evidence in outputs/rigorous/ with 8 scenarios, 8 policies, and 20 seeds per scenario.

5. Tune ASMF parameters

python scripts/tune_asmf.py --n-configs 200 --seed-spec 101:110 --top-k 3 --workers 3 --duration-scale 0.5

This is the targeted refinement step. On a 2 to 4 core laptop CPU, --workers 3 is a practical default; use --workers 2 if the machine is thermally constrained.

Outputs:

outputs/tuning/asmf_tuning_raw.csv
outputs/tuning/asmf_tuning_ranked.csv
outputs/tuning/top_variants.json

6. Run the final comparison

python scripts/run_final_comparison.py --variants-file outputs/tuning_speedcheck_w6/top_variants.json --seed-spec 101:120 --workers 3 --duration-scale 1.0

This compares baseline ASMF, tuned ASMF variants, and the main baselines, then writes:

outputs/final_comparison/final_results.csv
outputs/final_comparison/final_summary.csv
outputs/final_comparison/final_pairwise_vs_default.csv

7. Run the robustness check

python scripts/run_final_comparison.py --variants-file outputs/tuning_speedcheck_w6/top_variants.json --seed-spec 121:140 --output-dir outputs/final_comparison_robust --workers 3 --duration-scale 1.0

This repeats the final comparison on a disjoint seed block to verify that the tuned ranking holds on unseen runs.

Optional validation runs

These folders are for execution checks and debugging, not for the final report claims:

outputs/tuning_smoke/
outputs/final_comparison_smoke/
outputs/final_comparison_probe/
outputs/final_comparison_speedcheck/

Interpretation rules:

asmf_default is the baseline ASMF policy.
asmf_tuned_v1, asmf_tuned_v2, and asmf_tuned_v3 are tuned ASMF candidates.
gmsr, p2c, least_queue, and random are the comparison baselines.
Use the tuned-vs-default pairwise output to judge whether tuning helped.
Use the robustness run to verify the same ordering on unseen seeds.

How To Read The Results

When comparing policies, use this priority order:

Throughput for raw completion rate.
Average wait time for latency.
Backlog area and max queue for overload buildup.
Queries per decision and bytes transferred for coordination cost.

Current outputs support this practical summary:

gmsr and least_queue are strongest for raw throughput.
asmf_tuned_v2 is the strongest balanced ASMF variant in the current tuning set.
asmf_tuned_v2 improves over asmf_default on throughput, wait, and backlog.
asmf_no_sampling shows that sampling is essential; removing it hurts scalability sharply.

Parameter Selection Notes

The tuning campaign and the two-seed robustness comparison point to a stable ASMF region rather than a single fragile setting. The best balanced variant in the current outputs is asmf_tuned_v2.

Practical parameter range from the top tuned variants:

sample_k: 2 to 4, centered near 3
eta: about 0.006 to 0.019, centered near 0.012
threshold: about 0.109 to 0.139, centered near 0.126
min_correction: about 0.712 to 0.865, centered near 0.791
max_correction: about 1.306 to 1.626, centered near 1.492

Interpretation:

Smaller sample_k keeps routing cheaper, but going too low reduces search quality.
threshold in the low 0.12 range gives a good balance between acceptance and rejection under load.
max_correction matters most among the top tuned variants; larger values tend to align with better composite score.
eta should stay small; overly aggressive updates make the correction term unstable.

Scale Sensitivity Across Scenarios

The rigorous campaign shows that algorithm ranking changes with scale tier:

Small scale: ASMF variants reduce wait and backlog much more than gmsr or least_queue, while pure throughput is still led by least_queue and gmsr.
Medium scale: gmsr and least_queue lead on throughput and latency, while default ASMF is competitive but slightly behind on the main queueing metrics.
Large scale: most strong policies cluster tightly on throughput; gmsr, least_queue, p2c, and asmf family variants are close, but asmf_no_sampling degrades sharply.

This means the best policy depends on the deployment scale:

For small systems with tight queues, ASMF is the most attractive family.
For medium to large systems focused purely on throughput, gmsr or least_queue can edge out ASMF.
For balanced deployment with lower coordination cost, tuned ASMF is the preferred ASMF choice.

These results indicate that ASMF is particularly effective in smaller-scale and coordination-sensitive environments, while global-state policies retain advantages in fully informed, medium-scale regimes.

Limitations

ASMF does not outperform global-state policies such as gmsr and least_queue on latency and backlog in every scenario.
Performance is sensitive to parameter tuning, especially the feedback gain and resource weighting terms.
Multi-resource scoring can over-penalize decisions if calibration is too aggressive.
The results are simulation-based; real-world deployment effects such as network delay variability and partial failures are only approximated.

Outputs are generated in outputs/benchmark/:

benchmark_results.csv
benchmark_summary.csv
throughput_boxplot.png
wait_time_boxplot.png
backlog_boxplot.png
config_used.json

5. Run Tests

pytest -q

Policies Included

asmf: proposed algorithm
asmf_no_feedback: ablation (feedback correction removed)
asmf_no_sampling: ablation (global allowed set instead of sampled set)
asmf_no_multiresource: ablation (queue-only style scoring)
gmsr: oracle full-state baseline
p2c: power-of-k by shortest sampled queue
least_queue: global least queue in allowed set
random: random backend in allowed set

Rigorous Evaluation Coverage

Workloads: poisson, bursty, zipf_skew
Scale tiers: small (10 backends), medium (50), large (220)
Stress scenarios: backend failure, load spike, capacity degradation
Communication metrics: state_updates_sent, state_queries, bytes_transferred_est, queries_per_decision
Convergence metrics: convergence_time_ms, mean_queue_variance, oscillation_index

Academic Claims Supported

The experiments provide direct evidence for:

Sampling reduces coordination complexity to $O(k)$: removing sampling (asmf_no_sampling) substantially increases state queries and degrades latency, confirming sampling as a scalability mechanism.
Feedback provides adaptive correction: differences between asmf_default and asmf_no_feedback show feedback is useful but tuning-sensitive; small $\eta$ is required for stability.
Multi-resource scoring affects routing: asmf_no_multiresource shows mixed results across scenarios, confirming resource-awareness is important but requires careful weight calibration.
ASMF achieves competitive performance with significantly lower coordination overhead: tuned ASMF maintains near-baseline throughput while reducing queries per decision by ~80-90% compared to global-state methods.

Interpretation and Scope

These results demonstrate that carefully tuned, feedback-driven sampled routing can approach full-information performance in many regimes while significantly reducing coordination cost. However:

Results are simulation-based; real-world deployment effects (network variability, cascading failures, non-linear congestion) are only partially captured.
ASMF is strongest in coordination-sensitive environments (small scale, limited bandwidth) and less dominant in fully-informed, large-scale settings.
Global-state methods retain advantages for strict latency or backlog bounds when system-wide information is cheaply available.
Performance depends significantly on parameter tuning; the stable region (not a single point) is documented above.

Suggested Submission Package

Source code and tests
Benchmark outputs from outputs/benchmark/
Rigorous outputs from outputs/rigorous/ including:
- rigorous_results.csv
- rigorous_summary_ci.csv
- asmf_pairwise_improvements.csv
- pairwise_stat_tests.csv
- rigorous_time_series.csv
docs/PROOF_SIMULATIONS.md
docs/GITHUB_PUBLISH_PROTOCOL.md
Short report section citing ASMF equations and results

License

MIT

Name		Name	Last commit message	Last commit date
.github/workflows		.github/workflows
docs		docs
scripts		scripts
src/asmf_lb		src/asmf_lb
tests		tests
.gitignore		.gitignore
LICENSE		LICENSE
README.md		README.md
package-lock.json		package-lock.json
pyproject.toml		pyproject.toml
requirements.txt		requirements.txt

Latest commit

History

Folders and files

Repository files navigation