A method for replicating a deduplicated storage system is disclosed. A stream of data is stored on an originator deduplicating system by storing a plurality of deduplicated segments and information on how to reconstruct the stream of data. The originator deduplicating system is replicated on a replica system by sending a copy of the plurality of deduplicated segments and information on how to reconstruct the stream of data to the replica system. A first portion of the deduplicated segments stored on the originator deduplicating system that is corrupted is identified. A copy of the first portion of the deduplicated segments is requested to be sent by the replica system to the originator deduplicating system.