2
$\begingroup$

In the paper "Causal Memory: Definitions, Implementations, and Programming (Distributed Computing [DC] 1995)", the authors present a formal definition of causal memory, an abstraction of distributed shared memory that ensures that processes in a system agree on the relative ordering of operations that are causally related.

More interestingly, it is shown that data-race free (DRF, for short) programs, if written to run correctly on sequentially consistent memory, also run correctly in a system with causal memory. That is,

DRF theorem: If program $\Pi$ is data-race free, then all histories of $\Pi$ when run on causal memory are sequentially consistent.

For completeness, the definition of data-race free is given as follows. For more details and discussions, you can refer to “Data-race free” programs at cs.se.

DRF: Program $\Pi$ is data-race free if, for all histories $H$ of $\Pi$ and all causality orders $\leadsto$ of $H$, if $H$ has a serialization that respects $\leadsto$ (note that this implies that $H$ is sequentially consistent), then $H$ is data-race free with respect to $\leadsto$.

This theorem is important and beneficial to programmers because data-race free programs can be written assuming a sequentially consistent memory even for a system that provides causal memory.

Despite such "equivalence" DRF theorem, I am still curious about the detailed behaviors of data-race free programs when run on causal memory and on sequentially consistent memory. Formally,

My problem: Let $\Pi$ be a data-race free program. When run on causal memory, $\Pi$ results in a set (denoted $E_{c}$) of (possibly infinite many) executions. When run on sequentially consistent memory, it results in a set (denoted $E_{s}$) of (possibly infinite many) executions. Though, according to DRF theorem, every execution in $E_{c}$ is sequentially consistent, are the two sets of executions equal, i.e., $E_c = E_s$?

This problem is essentially inspired by the paper "Linearizable Implementations Do Not Suffice for Randomized Distributed Computation" (arXiv for STOC'2011), which shows that linearizability does not suffice for randomized algorithms. Specifically, using well-known linearizable implementations of objects in place of atomic objects can change the probability distribution of the executions (and thus the outcomes).

I want to investigate whether such phenomenon happens in the context of data-race free programs on different memory models. Here the data-race free programs may be deterministic or randomized which permit local coin-flips.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.