The budget of a campaign is stored centrally on Redis, right? Otherwise winning a bid and hitting the budget limit on one server would still not hinder other servers bidding for more
So why isn't the bidding amount subtracted from the budget when a server bids instead of when it wins. Naturally this means it has to be added again when the bid is lost, so there is slightly more overhead.
No overspending is possible in this case (substracting the budget must be an atomic operation naturally)
But I might be totally off. I don't understand your calculation that if 36 servers bid $99 with a total budget of $100 and all win, that they are $35 over limit and not 36*$99 -$100.