A data storage system includes multiple storage zones that store replicated copies of data items. Upon receiving a delete operation at a particular time to delete a data item, the system computes a maximum last update time based on the particular time and a minimum data item lifetime. Based on determining that a copy of the data item is stored in the data storage zone, the system then determines a last update time of the data item. In addition, based on determining that the last update time is less than the first maximum last update time, the system deletes the copy of the data item from the data storage zone.