A computer system that provides services to clients may be configured to determine whether it is operating in an overloaded state based on the percentage of client-specified quality of service (QoS) expectations that are not met. For example, if the percentage of service requests in a group of recently serviced requests for which client-specified expectations of a maximum response time were not met is greater than a pre-determined overload threshold, the system may be considered to be in an overloaded state. The overload threshold may be configurable. The overload state may be determined periodically by determining the percentage of service requests in a moving window of time for which client-specified QoS expectations were not met. In response to determining that the system is operating in an overloaded state, it may be configured to throttle at least a portion of incoming service requests in an attempt to exit the overloaded state.