Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for estimating distributed consumption of a quota. One of the methods includes receiving, by a first request processing server, a request having one or more specified characteristics; identifying a quota; determining, by the first request processing server, an actual number of requests having the one or more characteristics received by the first request processing server since a most recent synchronization with a parent server; generating, by the first request processing server, a current estimated total number of requests having the one or more characteristics that have been received; determining, by the first request processing server, that the quota has not been reached; and approving, by the first request processing server, the received request.