The reliability of a composite service having service components is determined, where the composite service can fail only where underlying resources fail. The composite service is represented as a plurality of continuous-time Markov chains (CTMC's). Each CTMC corresponds to a resource. A product of the CTMC's is constructed. The product encompasses composite service states. Steady-state probabilities for the product are determined. Each steady-state probability corresponds to a likelihood that a corresponding state will be a steady state. For each state of the composite service, a reward structure is determined. The reward structure corresponds to a likelihood that the state will successfully use the resources without failure. The reward structure is determined for a given state based on the given state's steady-state probability and based on discrete-time Markov chains (DTMC's) corresponding to the service components. The reliability of the composite service is determined based on the reward structure of each state.