Earlier quoted context omitted.
It's also a mostly solved problem because advertisers have budgets and it's common to implement globally distributed budget servers to avoid showing more ads than the advertiser paid for, despite tens of thousands of individual web servers needing to know which ads in their inventory have budget left. It's a fun exercise similar to global rate-limiting/load-balancing.
That is fascinating. If you have the time could you (anyone feel free) talk a bit about how you would implement a globally distributed budget? I can imagine a few simple options, but they all seem to have significant shortcomings.
Web servers check with the leaf nodes for every ad they want to show. If that leaf has a budget greater than zero it decrements its own budget and returns success. If the web server gets a success it shows the ad, if not it checks with another budget server or two. Web servers frequently log how many ads were served per client.
Whenever leases are up the intermediate nodes inform the parents of how much was spent and get a new lease. If nodes crash or otherwise don't return their lease then their parents have to assume the whole budget was spent, but leases are kept small to avoid big discrepancies.
If the root crashes then there are problems so the root can be a slow ACID replicated database as long as its immediate children are mostly reliable and take large enough leases to minimize load on the root.
Periodically web server logs are aggregated to adjust the root budgets to account for crashed intermediate nodes and web servers.
The tree approach allows global low latency operation guaranteeing no overspending and minimizing underserving. Nodes are provisioned from the leaves on up to handle the necessary amount of traffic and to ask for leases large enough for 99.X% percent of child requests to succeed.
Any cloud provider could use the same technology on individual hosts to grab leases of CPU, RAM, disk, etc. by the minute per user and terminate services with no budget. Leases could be a lot longer because most budgets are monthly to cover all service needs and not pathological ad campaigns with low budget, high bid, and huge audience.
It's up to cloud (or ad server) providers to decide whether to stop services if the budget system is broken. In most cases it makes sense to fail open and keep serving and eat the loss because shutting everything down will incur even bigger losses.