Systems and methods are described for managing requests for computing capacity from a provider of computing resources. The computing resources may include program execution capabilities, data storage or management capabilities, network bandwidth, etc. In some implementations, user requests are probabilistically denied or granted while some computing resources are still available. By denying some requests or granting only some, the rate of computing resource usage can be reduced, thus preserving some capacity for a longer period of time. In one embodiment, the capacity can be provided to clients based on client priority, provided to clients with reserved resources, provided to clients probabilistically, sold on a spot market, or allocated in some other fashion.