How does interdependent state logic work?
It works if the propagation delay (clock-to-Q) of the flip-flops involved is longer than the hold time of the flip-flops (plus any difference in arrival time in the clock signal between one flip-flop and another).

If this is true then when each clock cycle arrives, their outputs don't change for some time (the clock-to-Q delay). By the time the output of one flip-flop changes, the next flip-flop (whose input is connected to the output of the first one) has already "decided" what it is going to change to.

In programmable logic (CPLDs or FPGAs), this is often achieved using "negative hold time". That basically means that the next state of a flip-flop after a clock edge arrives is actually determined by the input a few 100 ps before the clock edge, rather than the input at the exact moment of the clock arrival. (Practically this really means the data is delayed by a few 100 ps from the notional input of the flip-flop to where it actually affects the flip-flop circuit)