PL-2L(monotonic-view) G-monotonic: experiment with adding the anomaly about elle

[aphyr]

I'm afraid I haven't worked at all on causal or PL-2L yet--nobody's actually asked me to check those properties yet. There's a few definitions in consistency-models.clj, but that's just as a "this can catch occasional anomalies and "having these partial definitions might be useful later if someone takes on these models in more detail" rather than "Elle knows about all forms of anomalies in every consistency model". It'd certainly be nice if it did, haha.

G-single and G-monotonic aren't interchangeable. Elle's G-single is taken directly from Adya's G-single definition, and is defined over DSGs. G-monotonic is defined over USG(H, T_i), which doesn't (presently) exist in Elle. They're not the same graph, which is probably why you're seeing Weird Results here. ;-)

G-single-process is a boundary anomaly for strong-session SI. Pulling it out into a weaker isolation level probably broke the BFS phase of the anomaly search. I imagine something like "the cycle existence pass says there was a strong-session-SI cycle, but also found no cycles that would arise in weaker isolation levels. From this we know that any search for boundary anomalies at levels lower than strong-session-SI are redundant, so we won't bother searching for G-single-process at all".

• monotonic-view's G-monotonic needs to be expressed, it's currently a no-op

Maybe? I don't personally have a need for it yet, but if it's important for your use case you could add it. The naive definition is O(n^2), so you'll want to do Something Clever (TM)--perhaps it could be unified with the internal passes in list-append and rw-register. I could be convinced to take a PR for this, but it needs to be relatively simple and not impose, say, huge performance/memory penalties on the rest of the system. Either that or we put it behind a flag.

causal, consistent-view, has to end up with process order

Maybe. I'm not sure about that one. Would need to look carefully at the formalism's event order and prove it's equivalent to process order plus whatever additional constraints--they're not the same.

G-monotonic, as G-single-process, would more correctly identify what consistency level you are...

I'm afraid not--they're not the same anomaly. I'm not sure exactly all the ways this would cause Elle to be wrong, but it would definitely be wrong in some ways. ;-)

[nurturenature]

Thanks for such an informative response!
Now I can see how dropping an arbitrary anomaly into a model would cause such weirdness, and not be what is really wanted.

I will try creating a USG, use a PL-2L-cycle-exists, etc, and report back.

The naive definition is O(n^2), so you'll want to do Something Clever (TM)
it needs to be relatively simple and not impose, say, huge performance/memory penalties

Thinking comparable to the other cycle-exists in performance and implementation.
If it can't be optimized and/or unified with the existing work being done, it's probably not a good candidate for inclusion.