Reliability monitoring can be performed for compute instances in a cluster with auto-scaling capability. Such monitoring can analyze state information for various instances, such as spot instances, to determine when an interruption or termination is to occur. An impact assessor can determine the impact on performance due to any such interruption or termination, and if necessary to maintain at least a minimum level of performance then an action performer can obtain additional or alternate instances, which may be of a different type, to make up for lost capacity. Any tasks being performed can be migrated to the newly-allocated instances without any failures or significant impact on performance, and the previously-utilized instances can be released corresponding to the termination or interruption.