In the near future, the number of cross-organizational automated interactions or processes (B2B) is expected to increase strongly along with the trend to outsource non-core business tasks. Furthermore, the possibility of offering new services or processes based on the composition of both internal and external services is raising this number even faster. For example, among the enabling technologies the so-called "web services", allowed the number of available commercial services to grow rapidly. However, these systems raise some unique software engineering problems that are related to their connected component's evolution. Cross-organizational services can be compared to distributed component systems with distributed maintenance responsibilities. Consequently, for the entire system to stay coherent, the consumers and providers of cross-organizational services must be bound by contracts. Moreover, these contracts must include some temporal specification of the availability of services. In this paper, we highlight the relationship between existing distributed component system technologies and cross-organizational services. We also explore different service evolution scenarios. After having defined the notion of dependency graph for a service, we analyze how temporal availability can be specified and show a way to compute the availability of an offered service given the availability of the consumed services on which it depends.