Randomized Algorithms for Fair Load Distribution in Distributed Systems

Abstract

Fair load distribution is a persistent challenge in distributed systems where heterogeneous resources, bursty arrivals, and partial system knowledge can cause skewed utilization and tail-latency blowups. Randomization—through task placement, sampling, and contention resolution—provides lightweight mechanisms to break adversarial patterns and improve fairness without heavy global coordination. This manuscript examines randomized algorithms for fair load distribution across clusters of stateless and stateful services. After defining operational fairness and its measurement via Jain’s index, Gini coefficient, coefficient of variation, and tail latency, we review core techniques: uniform random assignment, the “powerof-d choices,” randomized work stealing, consistent hashing with virtual nodes, randomized dispatch queues, and gossip-style load exchange.  We then outline a simulation methodology that varies arrival processes (Poisson and heavy-tailed), servicetime distributions, heterogeneity. scale-out Statistical dynamics, and analysis compares algorithms using non-parametric tests and effect sizes. Results show that two- or three-choice sampling achieves near-equalized utilizations with modest coordination overhead; randomized work stealing excels in burst absorption; and consistent hashing with adequate virtual nodes preserves state locality while keeping imbalance low under churn. We conclude with design guidance: pick d-choice sampling for stateless RPC services at moderate load; combine consistent hashing and limited random probing for stateful shards; enable opportunistic stealing for bursty, CPU-bound workloads; and use randomized backoff and admission control to maintain fairness under overload. The scope and limitations section clarifies generalizability, sensitivity to realistic network effects, and implications for multitenant fairness and energy-aware scheduling.