Mastodawn

Oliver Kennedy Jul 24, 2025

Concurrency protocol question to those with more experience in the space than I.

Classical OCC requires *transitive* conflict serializability. That is, the conflict graph can not contain cycles *at all*. I think one of my students and I might have just found a setting where pairwise conflict serializability suffices.

To be more precise, take three transactions: A, B, C. A reads from B's write set, B reads from C's write set, and C reads from A's write set (but not visa versa). There's a cycle in the conflict graph, so these three transactions are *not* conflict serializable.

However, because there is no *pairwise* cycle, in our setting, all three transactions executed concurrently on a single snapshot result in three write sets that, when merged, are guaranteed to be equivalent to a serial execution of the three transactions.

This feels weird...

1. Are we correct that this is weird?
2. Has anyone else seen/done something similar?

Show thread

Dan Ports Jul 24, 2025

@okennedy Why do you say that the results are equivalent to a serial execution of the three transactions? That doesn't seem like it would be true in general, but maybe I'm missing something.

Show thread

Oliver Kennedy Jul 25, 2025

@dan Yeah, this isn't the case in general. We have a bit of a niche use case where

1. We only create transactions that are guaranteed to commute, so A(B(db)) = B(A(db))
2. Merging the effects of transactions is commutative, so db + δA(db) + δB(db) = db + δB(db) + δA(db)

It wasn't immediately obvious to us, but we seem to be able to prove that these two constraints imply that the A, B, C cycle can be safely executed on a single snapshot:
db + δA(db) + δB(db) + δC(db) = A(B(C(db)))

Show thread

Oliver Kennedy

After my brain's had a chance to chew on this problem, the A(B(db)) = B(A(db)) property turns out to be *really* strong.

We're looking at transactions in the context of IVM, where this sort of thing makes sense (maintaining a view had better be independent of insertion order). However IVM schemes like #DBToaster achieve this by having triggers that read from at least one relation that every other trigger writes to. No proof yet, but I'm pretty sure that such pairwise dependency cycles are a necessary condition for A(B(db)) = B(A(db)).

All that to say that I don't think we've found some form of OCC that can magically employ commutativity to avoid inter-transaction data dependencies.

However, guaranteeing that all conflicts will be pairwise means that we *can* avoid (without loss of precision) the need to compute a transitive closure on the committed transaction graph to find conflicts. That seems neat.