A method may be performed by a device of a group of devices in a distributed data replication system. The method may include storing objects in a data store, at least one or more of the objects being replicated with the distributed data replication system, and conducting a scan of the objects in the data store. The method may further include identifying one of the objects as not having a reference pointing to the object, storing a delete negotiation message as metadata associated with the one of the objects, and replicating the metadata with the delete negotiation message to one or more other devices of the group of devices.