Patent ID: 8667499

Claim:
A computing system configured to manage execution of programs for users, the system comprising: a capacity request manager component that is configured to manage requests for execution of programs for users of a program execution service having a plurality of computing nodes, at least some of the plurality of computing nodes comprising physical computing devices, the capacity request manager component configured to: receive from a user of the program execution service a request to provide a computing resource associated with one or more of the plurality of computing nodes; determine availability of the requested computing resource on the plurality of computing nodes; and probabilistically grant the request if the determined availability is below a first threshold, wherein a probability of granting the request is based at least in part on the availability of the requested computing resource and a probability function that is used to determine the probability of granting the request, such that at least some requests to the program execution service are denied based at least in part on the probability function, even if available resources exist.