Re: hb: potential causality; causal order: explicit causality?
Shuyang Liu via Concurrency-interest <[email protected]> Wed, 2 Mar 2022 12:20:40 -0800 (PST)
| Newsgroups | gmane.comp.java.jsr.166-concurrency |
|---|---|
| Message-ID | <[email protected]> |
--===============9128975228429770200== Content-Type: multipart/alternative; boundary="----=_Part_11950667_1622785611.1646252440229" ------=_Part_11950667_1622785611.1646252440229 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Hello, I cannot give an exact answer to the question but the definition of the term "causality" is quite ambiguous in weak memory models as it is very easy to raise to the out of thin air issue if not defined carefully. Perhaps a good reference is not a definition but a set of litmus tests showing how "causality" works in Java: http://www.cs.umd.edu/~pugh/java/memoryModel/CausalityTestCases.html For Java, it can be hard to decided whether certain access "doesn't influence the value written" because of the compiler optimizations. Sometimes a compiler can even eliminate a control dependency between two events due to common sub-expressions so some of the explicit causal order at source code level may not be preserved by the compiler. On that front, I found this recent paper to be really close to formally define the dependencies: https://dl.acm.org/doi/10.1145/3498716 Best Regards, Shuyang From: "concurrency-interest" <[email protected]> To: "concurrency-interest" <[email protected]> Sent: Saturday, February 26, 2022 5:36:05 AM Subject: [concurrency-interest] hb: potential causality; causal order: explicit causality? Hi, I'm trying to get a better understanding of the causal order. So I'm posting my understanding of the topic and would like to get feedback if I'm on the right track. There are 2 flavors of causality in the space of memory models and distributed systems: - potential causality - explicit causality In the "Time, clocks, and the ordering of events in a distributed system", where the happens-before relation is introduced, Leslie Lamport is talking about potential causality. So if a->b then a might have affected b. The happens-before relation from the JMM is about potential causality as well. E.g. thread1: r1=a (1) a=1 (2) They are ordered by the happens-before relation due to the program order rule. The happens-before has no clue if (1) and (2) are causally related or not; so it just assumes that (1) might have affected (2). Every execution that is allowed by the JMM has the following 2 constraints: - (happens before) consistency. - causality The primary purpose of causality is to exclude executions with causal loops. AFAIK this causal order is explicit causality. E.g. thread1: r1=a (1) a=1 (2) The read (1) doesn't influence the value written at (2), so they are not ordered by the causal order. But the following example is one with explicit causality: thread1: r1=a (1) a=r1+1 (2) The value written is influenced by the value read, so (1) is ordered before (2) in the causal order. Is my understanding correct? PS: One of the papers I'm studying is the "JSR-133 Java Memory Model and Thread Specification". Regards, Peter. _______________________________________________ Concurrency-interest mailing list [email protected] http://cs.oswego.edu/mailman/listinfo/concurrency-interest ------=_Part_11950667_1622785611.1646252440229 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable <html><body><div style=3D"font-family: arial, helvetica, sans-serif; font-s= ize: 12pt; color: #000000">Hello,<br><br>I cannot give an exact answer to t= he question but the definition of the term "causality" is quite ambiguous i= n weak memory models as it is very easy to raise to the out of thin air iss= ue if not defined carefully. Perhaps a good reference is not a definition b= ut a set of litmus tests showing how "causality" works in Java: http://www.= cs.umd.edu/~pugh/java/memoryModel/CausalityTestCases.html<br><br>For Java, = it can be hard to decided whether certain access "doesn't influence the val= ue written" because of the compiler optimizations. Sometimes a compiler can= even eliminate a control dependency between two events due to common sub-e= xpressions so some of the explicit causal order at source code level may no= t be preserved by the compiler. On that front, I found this recent paper to= be really close to formally define the dependencies: https://dl.acm.org/do= i/10.1145/3498716<br><br>Best Regards,<br>Shuyang<br><br><hr id=3D"zwchr" d= ata-marker=3D""><div data-marker=3D""><b>From: </b>"concurrency-interest" &= lt;[email protected]><br><b>To: </b>"concurrency-intere= st" <[email protected]><br><b>Sent: </b>Saturday, Fe= bruary 26, 2022 5:36:05 AM<br><b>Subject: </b>[concurrency-interest] hb: po= tential causality; causal order: explicit causality?<br></div><br><div data= -marker=3D""><div dir=3D"ltr"><div>Hi,</div><br><div>I'm trying to get a be= tter understanding of the causal order. So I'm posting my understanding of = the topic and would like to get feedback if I'm on the right track.<br></di= v><br><div>There are 2 flavors of causality in the space of memory models a= nd distributed systems:<br></div><div>- potential causality</div><div>- exp= licit causality</div><br><div>In the "Time, clocks, and the ordering of eve= nts in a distributed system", where the happens-before relation is introduc= ed, Leslie Lamport is talking about potential causality.</div><br><div>So i= f a->b then a might have affected b.</div><br><div>The happens-before re= lation from the JMM is about potential causality as well. E.g. <br></div><b= r><div><div>thread1:<br></div><div> r1=3Da (1)<br></div><div> a= =3D1 (2)</div><br></div><div>They are ordered by the happens-before r= elation due to the program order rule. The happens-before has no clue if (1= ) and (2) are causally related or not; so it just assumes that (1) mi= ght have affected (2).</div><br><div>Every execution that is allowed by the= JMM has the following 2 constraints:</div><div>- (happens before) consiste= ncy.</div><div>- causality<br></div><div>The primary purpose of causality i= s to exclude executions with causal loops.</div><br><div>AFAIK this causal = order is explicit causality. E.g.</div><br><div><div>thread1:</div><div>&nb= sp; r1=3Da (1)<br></div><div> a=3D1 &nbs= p; (2)<br></div><br><div>The read (1) doesn't influence the value written a= t (2), so they are not ordered by the causal order.<br></div><br><div>But t= he following example is one with explicit causality:</div><br><div><div>thr= ead1:</div><div> r1=3Da (1)<br></div><d= iv> a=3Dr1+1 (2)</div><br><div>The value written is influenced = by the value read, so (1) is ordered before (2) in the causal order.</div><= br><div>Is my understanding correct?<br></div><br><div>PS: One of the paper= s I'm studying is the "JSR-133 Java Memory Model and Thread Specification".= <br></div><br><div>Regards,<br><br></div><div>Peter.<br></div><br><br><br><= /div></div></div> <br>_______________________________________________<br>Concurrency-interest= mailing list<br>[email protected]<br>http://cs.oswego.edu= /mailman/listinfo/concurrency-interest<br></div></div></body></html> ------=_Part_11950667_1622785611.1646252440229-- --===============9128975228429770200== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Concurrency-interest mailing list [email protected] http://cs.oswego.edu/mailman/listinfo/concurrency-interest --===============9128975228429770200==--