Skip to content
#edge computing Preprint

Minimizing Bottleneck Overload Risk in Online Edge Task Placement under Workload Uncertainty

Nov 2026 · 0 citations · 47 references
Computer Science

TL;DR

RBP places tasks in descending order of standard deviation, each on the server with the smallest post-assignment risk ratio, and refines the assignment with relocations and swaps within a finite per-period online budget, and minimize the largest risk ratio, attained at the risk bottleneck.

Abstract

In edge computing, tasks must be placed on servers of finite capacity before workloads are realized, often with only workload means and variances known. An assignment balanced on expected load can still leave a server with more fluctuations than its residual capacity can absorb. Per-server risk constraints can enforce a prescribed overload tolerance but do not distinguish the assignments that meet it by how close the riskiest server comes to the limit. We show that, for independent tasks, placement preserves a period's total variance and total residual capacity, and decides only how fluctuation, measured by standard deviation, is paired with residual capacity across servers. The risk ratio, the ratio of fluctuation to residual capacity, parameterizes a server's worst-case overload probability over all aggregate workload distributions with given mean and variance. We minimize the largest risk ratio, attained at the risk bottleneck. Risk-Bottleneck Placement (RBP) places tasks in descending order of standard deviation, each on the server with the smallest post-assignment risk ratio, and refines the assignment with relocations and swaps within a finite per-period online budget. On small instances solved exactly by enumerating every assignment, minimizing the maximum expected utilization leaves the largest risk ratio 25.66-29.19% above its exact minimum on average, even with risk-minimizing tie-breaking, and the corresponding gap for RBP is 1.77-2.64%. In trace-derived multi-period simulations at two workload pressures, RBP reduces the worst-server overload probability by 26.0% and 18.0% relative to the best baseline and remains the lowest at every tested pressure and scale.

View source

Similar papers

Open access Oct 2026

Online Allocation with Heterogeneous Supply and Minimum Workload Guarantees

Keeping Gig Workers Working How should platforms allocate jobs when workers need a minimum amount of work to stay engaged? In their accepted paper, “Online Allocation with Heterogeneous Supply and Minimum Workload Guarantees,” Garud Iyengar and Raghav Singal study this question in online labor marketplaces, where work...

Garud Iyengar, Raghav Singal · 0 citations
Open access Oct 2026

Capacity Costs of Probability Ambiguity and Support Rectangularization in Edge–Cloud Scheduling

Edge–cloud task scheduling reserves uplink capacity before the wireless service state is known. The reserve depends on both the probability law over a prescribed service-state library and the geometry representing that library. This study separates and quantifies these two effects in a fixed-workload finite-state model...

Mikail Mohammed Salim, F. Naaz · 0 citations
#machine learning Preprint Oct 2026

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm

This paper proposes WISE (Widest Interval Selection with Elimination), achieving rate-optimal queue length regret at every sufficiently large time without knowing the horizon, and proves another lower bound that quantifies the increase in regret as the normalized capacity slack decreases.

Seoungbin Bae, Dabeen Lee · 0 citations
Preprint Nov 2026

Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness

Dominant Resource Fairness (DRF) is an influential policy for sharing multiple resources among jobs with heterogeneous demands. It combines sharing incentive, strategy-proofness, envy-freeness, and Pareto efficiency, making it particularly attractive for shared computing systems. DRF has been implemented in major resou...

Mugen Blue, Sung-Jin Im, Alexander Lindermayr · 0 citations
Sep 2026

Load Balancing with Partial Queue Information - Threshold Optimality and Indexability

We consider the problem of load balancing in a system with one dispatcher and $N$ parallel servers. The dispatcher must select one server to dispatch new jobs at every time-step and each server buffers incoming jobs in a queue. However, the dispatcher does not know the servers'backlogs and must make dispatching decisio...

Sathwik Chadaga, E. Modiano · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Oct 29, 2026

Microsoft Research Focus – Edition #97

Host Sowbhagya Suresh shares some of the latest news and cutting-edge research from across Microsoft—from understanding the challenges facing coding agents to uncovering how people use AI at work and improving extended-range weather forecasting. The post Microsoft Research Focus – Edition #97 appeared first on Microsoft Research.

MIT News · Artificial Intelligence Oct 28, 2026

Making machines that can listen

Professor Paris Smaragdis develops computers with superhuman hearing for applications like speech recognition, music understanding, and environmental monitoring.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.