Load Balancing with Duration Predictions
summary
Proposes an online algorithm for temporary jobs on unrelated machines that uses job duration estimates but not exact times, proving a competitive ratio of roughly log m + log D (with p ≈ log m) when estimates are within a small multiplicative error: if error is constant (e.g. 2) the bound matches the clairvoyant case. The method is almost-greedy on the L_p norm and crucially pretend duration = max possible instead of using raw estimates; results are theoretical upper/lower bounds, gaps remain (μ vs √μ).
AI-written summary · about
chapters (10)
- 0:00Load balancing research intro
- 3:50Online load balancing
- 6:24Dynamic load balancing
- 9:15Clairvoyant vs non-clairvoyant
- 12:04Duration estimation impact
- 17:40LP-norm generalization
- 21:02Algorithm intuition
- 25:27Summary of results
- 26:10Open questions
- 32:15Q&A
related talks
35mPredictable Latency
15mSound Dynamic Deadlock Prediction in Linear Time
21mWhat happens-after the first race? enhancing the predictive power of dynamic race detection
40mTurn Hours into Seconds- Concurrent Event Processing
42mRuntime scheduling: theory and reality
15mLearning-Based Controlled Concurrency Testing
31mClojure Parallelism Beyond Futures
01h 02mThread pools: variety of algorithms and features