Modelling API rate limits as diophantine inequalities

Summary

modelling API rate limits as diophantine inequalities You're allowed 10 requests per hour. Each task you run makes three attempts: initial call, retry after 10 minutes, and retry after 30 minutes. What’s the maximum number of tasks you can safely run per hour? Most engineers throw exponential backoff at the problem. And it works great in most cases! But can we, for the sake of having fun, be more mathematical about this? In a way, this is just an integer feasibility problem. the setup Let’s define the retry pattern: [0, 10, 30]. Every task fires three requests: at minute 0, 10, and 30 after its start. Now, suppose you start a new task every 20 minutes: Task A: starts at 0 → hits at [0, 10, 30] Task B: starts at 20 → hits at [20, 30, 50] Task C: starts at 40 → hits at [40, 50, 70] Now, examine the 60-minute window [30, 90]: Task A contributes 1 (at 30) Task B contributes 2 (at 30, 50) Task C contributes 3 (at 40, 50, 70) Total: 6 requests in that window. What if you had 4 such tasks? Or 5? At some point, that window exceeds the limit. the equation Let's generalise this. You start X tasks at time T. Each task has known retry offsets. For any time window [T, T + 60], you count how many of those retries land inside it. Then, Let Xi be the number of tasks started at time Ti. Let Ai be the number of attempts for those tasks that fall into our window. Let R be the rate limit of our window. Therefore, we are looking at, sum(Ai * Xi) <= R This is a bounded integer linear inequality. In other words: a diophantine inequality. a quick detour into diophantine inequalities We've now got the building blocks: retry timings and rate limits. But before we dive into the scheduling logic, let’s take a short detour into something older and surprisingly relevant: Diophantine equations. A Diophantine equation is just an equation where you’re only allowed integer solutions. Think 3x + 5y = 14, and you're asked to find values of x and y that are whole numbers. These types of problems show u...