A data storage system includes multiple zones that comprise separate geographic storage locations and store replicated copies of data items. Upon receiving a delete operation at a local zone at a time td, if a copy of the first data item exists in the local zone, the system computes a maximum last update time tmlu=td−tmin, wherein tmin is a minimum lifetime for a data item. Next, the system determines, from a local index, a time tlu that the first data item was last updated. If tlu