1. A method comprising: forming a first contract between a cooperating deduplicator and a first primary deduplicator to communicate any additions, deletions, or modifications to their respective deduplicator's information; forming a second contract between the cooperating deduplicator and a second primary deduplicator to communicate any additions, deletions, or modifications to their respective deduplicator's information; receiving an indication that a data is to be deleted; mapping the data to a segment; compiling a union of primary segment lists associated with both the first primary deduplicator and the second primary deduplicator at least in part by using the first contract and the second contract, wherein each primary segment list is associated with the segment; comparing the union of primary segment lists to a secondary segment list associated with the cooperating deduplicator, wherein the secondary segment list is associated with the segment; and using the comparison to identify the segment as no longer referenced by any of the first primary deduplicator and the second primary deduplicator.