My understanding is that validators can be made only responsible for the availability of the 25 collations that are immediate ancestors of their own (plus of course their own collation itself); so they can simply store this data until the challenge period runs out.