•Nondeterminator
has two parts:
–Check whether
threads are logically parallel
–Use shadow
spaces to detect determinacy race
•SP-Bags algorithm uses
LCA lookup to determine
whether two threads are parallel
•LCA lookup with
disjoint-sets data structure takes
O(α(v,v)) time.
•We do not care about the LCA. We just want to know if two threads are
logically parallel.