In the seminal paper "Causal memory: definitions, implementations, and programming", distributed causal memory is defined to ensures that all the processes in a system agree on the relative ordering of operations that are causally related.

Its implementation:

For its implementation, each process maintains a private copy of the abstract shared causal memory. All the processes are peer-equivalent, each of which invokes (as a client) and handles with (as a server) read/write operations locally and communicates asynchronously with each other. The scenario is depicted in the following figure.

Vector clocks are used for causality tracking among operations. The key point I am concerned with is that the implementation (in section 5) keeps one entry in each vector clock per client.

Extending it to wide-area distributed data storage system:

Now consider a wide-area distributed data storage system that aims to implement a causal memory. I have the following problems concerning about the scalability of the implementation mentioned above.

My problems:

  1. The clients in such system can be enormous and even unpredictable. Does this mean that it is not practical (if not impossible) to adopt the vector clock mechanism that keeps one entry per client?
  2. If the vector clock keeping one entry per client is not feasible, how to track the causality among operations? Are there any research papers or systems on this issue?
  3. The architecture depicted in the figure is definitely not applicable to the wide-area distributed data storage system because we cannot simply provide an exclusive server for each client. Then, what are the appropriate architectures in this situation?

p2p_localarea_replication http://i1.tietuku.com/26a4136815e1ff37.png


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.