In one embodiment, a service mediator provides a service that is a composite of atomic services and executes a recovery pattern in the event that a service is not available. More particularly, in an initial phase of operation, the service mediator determines one or more recovery patterns for each atomic service offered in the composite service and stores in a database an identity of each such recovery pattern for each atomic service. In subsequent operation, the service mediator monitors the availability of each atomic service. When a user inquires of a composite service, the service mediator determines if any of its atomic services is unavailable. If an atomic service is unavailable, the service mediator selects a recovery pattern and executes it.