Someone implemented a fairly naive DAG in our system that sometimes sprouts cycles. The cheapest way to catch cycles is to limit the graph size to 10x nominal. If we ever encountered a request that was legitimately that far from normal, we would most likely time out during the subsequent work anyway, because processing time grows faster than n and our timeout is only about 20x our mean response time.

If there is a loop, we will hit the limit while evaluating the cycle because it’s a DFS. With a BFS we could hit the limit in a sibling of the problematic node.

Scheduling budgets are how most people avoid the halting problem. You set a fixed multiple of expected halting time and work hard to make sure that’s your p99 time instead of your p75 time, and stop trying to violate core principles of computational theory.