An access node of a distributed service collects workload data pertaining to at least one peer group of access nodes established for handling client requests. During a particular load shedding analysis, the access node uses the collected metrics to detect that a triggering condition for load shedding with respect to a set of persistent client connections has been met. Each persistent client connection is set up to be usable for a plurality of client requests. The access node initiates a phased termination of at least one selected persistent client connection. The phased termination comprises allowing completion of in-flight requests on the connection and rejecting new requests on the connection.