Assumptions:

1. There are many budgets, each for a different type(*) of request.
2. All the requests arrive at the same place and are distributed to the 36 boxes via some kind of load-sharing mechanism.
3. There is some mechanism -- I'm using time/amount below; but a "bid id" or similar, would work as well if not better -- for relating successful bids back to a list of outstanding bids.
4. Update: also assumes that you do not receive explicit notifications for failed bids -- hence the need to track them.

   When the budget manager is discarding unsuccessful bids, following the receipt of a success, it can use the values of the failures to adjust its bidding strategy.

Solution:

• Re-gig the load-sharing mechanism to route all requests of a particular type to one box.
• Each box can service multiple request types, but only one box ever services a particular request type.
• Each box requests (from the Redis box), the current budget for each of its request types, and stores them locally.
• As requests arrive, the servicing box can make bids up to but not beyond (or perhaps beyond, but only by some wiggle factor) the current budget for that type, and it decrements its local copy of the appropriate budget accordingly.

  It also maintains a list of time + amount for each bid it makes.

• When notifications of successful bids arrive they are routed directly to the redis box; or another dedicated box charged with maintaining the actual budget within the redis box, and the redis copy of the budget is decremented by the accepted bids.

  When the Redis manager receives notification of a successful bid, it sends notification of the amended real budget, and the amount and time of the successful bid to the machine charged with make bids for that budget.

  It can then discard all outstanding bids prior to the successful one; and apply those still outstanding to the amended real budget to obtain a new local copy.

This should allow the mechanism to bid as often as possible, whilst keeping the outstanding bid totals within the specified budget (or budget + wiggle).