Abstract: Adaptive software that can react to changes in the execution environment or user requirements by switching algorithms at runtime is powerful yet difficult to implement, especially in distributed systems. This paper describes a software architecture for constructing such adaptive software and a graceful adaptation protocol that allows adaptations to be made in a coordinated manner across hosts transparently to the application. A realization of the architecture based on Cactus, a system for constructing highly configurable distributed services and protocols, is also presented. The approach is illustrated by outlining examples of adaptive components from a group communication service.