Service-oriented architecture (SOA) promises an elegant model that can easily handle dynamic and heterogeneous environments such as pervasive computing systems. However, in reality, frequent failures of resource-poor and low-cost sensors greatly diminish the guarantees on reliability and availability expected from SOA. To provide a framework for building fault-resilient, service-oriented pervasive computing systems, we present a solution that combines a virtual sensor framework with WS-Pro/ASCT, a service composition mechanism. The use of virtual sensors enhances the availability of services, while the service composition solution ensures that the system can efficiently adapt to changes and failures in the environment. This approach also includes a novel probe-based monitoring technique for proactive collection of performance data and a Finite Population Queuing System Petri Net (FPQSPN) for modeling the performance of composed services. © 2009 Springer-Verlag US.