For one thing we look at both inbound and outbound traffic and we treat it separately. That use case looks different if we are trying to "test" TODO or if the TODO service is a backend that our app relies upon.

So if you mean that we want to "test" TODO, our analyzer looks for data in subsequent requests that was provided by the system-under-test (SUT) in previous responses. A common example of this is an HTTP cookie. The SUT gives us a session id through the Set-Cookie header response. So in a subsequent request we use the cookie from the app, not the one that was recorded. This has been done in general way to look for tokens.

Of course nobody is perfect so we'd love to see your real world app and test our algorithms against it. :)

I don't think that qualifies as non-determinism. This is just dependencies between operations.

Non-determinism would be, for example, something that's time-sensitive. If some result varies by time, then the only way to test it is to include time as a parameter. This can be complicated if the time variable plays into asynchronous updates (e.g. you want to test that a POST update worked, but it's actually eventually consistent). Caching (e.g. through Varnish or a CDN) would be another thing to make such tests much more complicated.

Another example is an API that has side effects. For example, a stock trading API might read real time quotes from another service. A stock trade then alters the next quote.