Patent ID: 8346820

Claim:
A method performed by a device of a plurality of devices in a distributed data replication system, the method comprising: storing objects in a data store associated with the device, at least one or more of the objects being replicated within the distributed data replication system; conducting a scan of the objects in the data store; identifying one of the objects as not having a reference pointing to the one of the objects; storing based on identifying the one of the objects as not having the reference pointing to the one of the objects, a delete negotiation message as metadata associated with the one of the objects; writing, to the metadata: a negotiation message indicator to initiate a delete negotiation associated with the one of the objects, a data store identifier to identify the data store as initiating the delete negotiation message, and a negotiation request identifier to identify the delete negotiation message; and replicating the metadata with the delete negotiation message to one or more other devices of the plurality of devices.