A disclosed method is performed at a fault-tolerant object-based storage system configured to synthesize parity data in order to protect stored data from loss, the fault-tolerant object storage system including a plurality of storage entities each configured to store data on an object-basis. The method includes determining a first parity value for a first data block set of one or more data block sets, wherein the first data block set comprises one or more respective data blocks, each respective data block associated with a respective storage entity of the plurality of storage entities. The method further includes generating a first compressed parity indicator for the first data block set, corresponding to the first parity value, and storing the first compressed parity indicator in a stripe of parity data in place of the first parity value within a first block set comprising the first data block set.