Yes that's most likely a misunderstanding there - most heuristics I've used were very much deterministic. Non-determinism is evil, that I would agree - but heuristics aren't. As long as you understand they are heuristics and might fail/lead to suboptimal results.

Most internet APIs use timeouts. That's as nondeterministic as it comes.

Networks are non-deterministic by nature... Just like disk IO, but on networks it's in an entirely new level.

Which is why the first rule of distributed systems is "don't distribute your system"

Yes, the network is non-deterministic. The point of a reliable protocol is to make it the outcome deterministic despite any underlying non-determinism. So why include timeouts in your protocol which just adds back the non-determinism?