This paper studies the dynamic web service selection problem in a failure-prone environment, which aims to determine a subset of Web services to be invoked at run-time so as to successfully orchestrate a composite web service. We observe that both the composite and constituent web services often constrain the sequences of invoking their operations and therefore propose to use finite state machine to model the permitted invocation sequences of Web service operations. We assign each state of execution an aggregated reliability to measure the probability that the given state will lead to successful execution in the context where each web service may fail with some probability. We show that the computation of aggregated reliabilities is equivalent to eigenvector computation and adopt the power method to efficiently derive aggregated reliabilities. In orchestrating a composite Web service, we propose two strategies to select Web services that are likely to successfully complete the execution of a given sequence of operations. A prototype that implements the proposed approach using BPEL for specifying the invocation order of a web service is developed and served as a testbed for comparing our proposed strategies and other baseline Web service selection strategies.