Observe that the race detection algorithm in Figure 6 uses the result of a query only to compare it with the current vertex.
we may answer queries differently as long as any such sequence of comparisons leads to the same outcome. 