Random clocks on computation paths reveal new time reach limits
Random Clocks on Computation Paths]{Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
Computational Complexity
Summary
This work studies a special kind of 'random clock' that watches computer programs at unpredictable moments, including jumping forward, pausing, or stepping backward. The authors explore how far these clocks can see into the computation with limited looks and whether stepping back can help. They find that rare long jumps let the clock glimpse very far, even exponentially far in time, while clocks that frequently step back see less. Interestingly, stepping back can significantly extend how far the clock sees when jumps happen rarely, but not when jumps ignore position.
What this means in practice
- •For hardware designers: Clarify limits on sampling-based monitoring that can observe system computations with random timing and rare backtracking steps.
- •For software testers: Guide design of inspection methods that randomly sample program execution steps, including backward checks, to detect long-term behaviors.
A theory result. No direct application yet.
Authors
Farzad Didehvar, Saman Farhat
Abstract
We watch a computation only at moments chosen by a random clock that can leap ahead, pause, or step back, and we count looks rather than steps. How far can such a clock reliably see with polynomially many looks, and does stepping back help? Rare long leaps reach exponential and doubly exponential time, with infinitely many levels between polynomial and exponential time. A clock that tends to fall back sees only the start of the input, and below polynomial time we find infinitely many incomparable levels. Stepping back can help decisively. For clocks whose long leaps occur only at rare positions, no forward-only clock goes beyond polynomial time, while even single steps back raise the reach to exponential time. Stepping back cannot help, however, when the clock's leaps ignore its position.