1
$\begingroup$

In a book dedicated to distributed algorithms, I found the following definition - potential causality diagram is consistent with happens before diagram if potential causality relation between system events is a subset of happens-before relation. So far so good.

But then I have read following claim potential causality diagram equals to the set of happens before diagram to which it consistent with. But how that is possible? I mean that cardinality of potential causality relation is less than the cardinality of happens before relation to which it consistent with. How may potential causality relation be composed of union of such happens-before relations? I agree that potential causality relation may be composed of a set of happens-before relations, but from my point of view happens before relations in such case should be subsets of potential causality relations? Could you explain what I missed?

Update: Quotation from the book. "Given a potential causality diagram $(E, \xrightarrow{p})$, a happened before diagram $(E, \rightarrow)$ is consistent with it if $\xrightarrow{p}\subset \rightarrow$.

Figure 2.5

is consistent with

Figure 2.6

Observe that $e_2 ->f_4$ but $\neg(e_2 \xrightarrow{p} f_4)$. A potential causality diagram is equivalent to the set of happened before diagrams that are consistent with it.

Vijay K. Garg. Elements of Distributed Computing (Kindle Locations 301-302). Kindle Edition.

Improve this question
$\endgroup$
2
  • $\begingroup$ Welcome to CS.SE! Would it be possible to provide a citation from where you read that, and quote the relevant excerpt? It's possible that providing additional context might help someone give a better answer. $\endgroup$
    – D.W. ♦
    Jan 23, 2017 at 14:08
  • $\begingroup$ @D.W. I updated question. Thank you for suggestion ! $\endgroup$
    – Andrey Lomakin
    Jan 23, 2017 at 14:37

1 Answer 1

Reset to default
0
$\begingroup$

The book says "A potential causality diagram is equivalent to the set of happened before diagrams that are consistent with it." (emphasis added)

You seem to have interpreted that as "A potential causality diagram is equal to the union of happened before diagrams that are consistent with it." But that's not the same statement. I would suspect that this might be the cause of your confusion. Go back to the original statement and disregard the idea of taking the union, and see if you can make sense of the original statement.

Perhaps there is additional explanation or context after that sentence.

If not, perhaps the book is claiming there is a bijection between (a causality diagram C) and (the set of happens-before relations that are consistent with C). That claim sounds accurate. To construct the inverse map: given such a set of happens-before relations, take the smallest element in the set, and that's C.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for an explanation. It seems I got it from the rest of the book. The author uses consistent with as linearization of. So definitely usability diagram is equivalent to consistent happens before diagrams $\endgroup$
    – Andrey Lomakin
    Jan 23, 2017 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.