A recovery process allows a recovering replica in a replicated data storage system to recover from a current replica the changes to the data that it has missed during a failure while, at the same time, the system is processing new requests issued by the source. Sequence numbers, assigned by the source to write requests and stored by each replica in association with the data item that the write request modifies, are used by the recovery process to determine when a replica has missed one or more write requests and requires recovery. During recovery, the recovering replica ignores all requests directly received from the source, and replaces the contents of a data item with the data received from the current replica only if the newly received data item has a higher sequence number than the corresponding sequence number of the data item already stored in the recovering replica. It also updates data items in response to new write requests that are forwarded to it by the current replica. At the same time, the current replica continues to receive requests from the source, performs those requests, and forwards those write requests to the recovering replica. It also scans its data items and sends to the recovering replica those data items and associated sequence numbers that have a sequence number higher than the sequence number of the last consecutive write request sent by the source that the recovering replica received before missing a write request.