A method and apparatus for writing data to a tape is disclosed. A plurality of data segments are written onto a tape simultaneously. Any data segments written to the tape that needs to be rewritten are identified. Each data segment that needs to be re-written is accumulated. The accumulated data segments are written to tape when a full set of data segments have been accumulated. The re-written data segments each have a first field in a header that designates itself and a second field in the header that designates a second re-written data segment.