Para limitar o foco da pergunta, direi usar o Linux como SO e tar como o formato de compactação. É claro que o tempo de execução é importante, mas saber que o arquivo é válido é mais importante. Se você fornecer uma linha de comando, por favor, associe-se à documentação para ela e, dentro da sua resposta, explique cada segmento do comando.
Aha! Encontrou o que procuramos (o Google salva o dia)!
Verifique este link: link
Como você, o autor está procurando uma boa maneira de verificar o arquivo TAR. Ele propõe um método para fazer exatamente o que você está procurando e aponta para um software de script que faz a verificação para você.
Não é perfeito, mas é melhor que nada.
EDITAR : Parece que o VeriTAR ainda suporta arquivos TAR compactados.
O sinalizador --verify seria útil para você? GNU
Tags tar linux archiving data-validation