Group Abstract Group Abstract

Message Boards Message Boards

Causal Invariance versus Confluence

Posted 5 years ago

I have a question that has been bothering me since 2002: what is the full relationship between causal invariance (all causal graphs are isomorphic independent of update order) and global confluence (all branch pairs eventually merge). As is stated many places, confluence is a necessary condition for causal invariance, but can be easily seen to not be sufficient.

I ask since things like CausalInvariantQ seem to be checking confluence instead, and I've heard you say things on livestream like "because this rule contains inverses, it is causal invariant," however from working through some examples it seems that containing inverses only implies confluence. Similarly the Knuth-Benedix completion only produces confluent systems, and not causal invariant ones. On the flipside, from reading Jonathan's paper on GR, it seems clear that you often truly want causal invariance.

I've read all sections of NKS and the WPP introduction several times, and I'm not 100% on this. Does anyone have anyplace that can help clear this up?

POSTED BY: Brent Werness
4 Replies
Posted 5 years ago

Indeed---as I said, your examples are more more to the heart of the matter! The isomorphism class trick seems to just be a bandaid to me since if you just extend the rule I stated to throw off "dust" of disconnected hyper-edges with each update, this keeps track up update steps and explicitly breaks the isomorphism class fix while keep the exact same causal graphs as before (even to the degree the same causal graphs are generated for the same seed by your code ;) ). I'd be willing to bet you can pretty generically break isomorphism classes without breaking confluence.

POSTED BY: Brent Werness
Posted 5 years ago
POSTED BY: Brent Werness
Posted 5 years ago
POSTED BY: Max Piskunov
Posted 5 years ago

If it's any consolation, I'm confused as well. The only conclusion I can make is that the system being non-overlapping (i.e., there is no branching at all) implies both, but I don't think neither confluence nor causal invariance implies each other.

Any thoughts, @Jonathan Gorard?

My counterexamples are in this notebook:

POSTED BY: Max Piskunov
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard