This paper addresses the problem of constructing and managing highly available services for large, open distributed systems. A novel replication protocol is presented that satisfies two fundamental requirements of this environment. First, it hides replication from the service clients and secondly, it facilitates the dynamic reconfiguration of the server group. The protocol has been implemented and tested in the Regis distributed environment. The experimental results indicate that the cost of replication transparency is acceptable.