we have a way to detect if it's broken.

Do it by checksum. If the checksums don't match, then redownload the changed parts. This is also fully predictable, but it's also far faster.