A disclosed method is performed at a fault-tolerant object-based storage system including M data storage entities, each is configured to store data on an object-basis. The method includes obtaining a request to store N copies of a data object and in response, storing the N copies of the data object across the M data storage entities, where the N copies are distributed across the M data storage entities. The method additionally includes generating a first parity object for a first subset of M copies of the N copies of the data object, where the first parity object is stored on a first parity storage entity separate from the M data storage entities. The method also includes generating a manifest linking the first parity object with one or more other subsets of M copies of the N copies of the data object.