It is desirable that the smaller is the number of faults to hit a network, the faster should a network protocol recover. We study the scenario where up to k (for a given k) faults hit processors of a synchronous distributed system by corrupting their state undetectably.

In this context, we show that the well known step complexity model is not appropriate to study time complexity of time-adaptive protocols (i.e. protocols that recover from memory corruption in a time that depends only on the number of faults and not on the network size). In more details, we prove that for non trivial dynamic problems (such as token passing), there exists a lower bound of Ω(D) (where D is the network diameter) steps on the stabilization time even when as few as 1 corruption hits the system.

This implies that there exist no time adaptive protocol for those problems in the asynchronous step model, even if we assume that the number of faults is bounded by 1 and that the scheduling of the processors is almost synchronous (between two actions of an enabled processor, any other processor may execute at most one action).