Systems with multiple components managing storage may implement efficient storage reclamation. A storage reclamation event may be detected for a system component. An indication to a request dispatching mechanism may be made which indicates that the system component is unable to perform further tasks in order to perform storage reclamation. A storage reclamation operation, such as a stop-the-world garbage collection technique, or a service process restart may be performed to reclaim at least some storage. Upon completion of the storage reclamation operation, an indication may be made to the request distribution mechanism that the service process has resumed performing tasks for the system. In some embodiments, a gossip protocol communicating availability information to different nodes of a distributed system may provide information to schedule storage reclamation operations at different compute nodes of the distributed system.