Maintaining causal consistency in distributed shared memory systems using vector timestamps has received a lot of attention from both theoretical and practical prospective. However, most of the previous literature focuses on full replication where each data is stored in all replicas, which may not be scalable due to the increasing amount of data. In this report, we investigate how to achieve causal consistency in partial replicated systems, where each replica may store different set of data. We propose an algorithm that tracks causal dependencies via vector timestamp in client-server model for partial replication. The cost of our algorithm in terms of timestamps size varies as a function of the manner in which the replicas share data, and the set of replicas accessed by each client. We also establish a connection between our algorithm with the previous work on full replication.
@cite_1: In recent years there has been a growing interest in developing communication systems that are able to deliver messages respecting potential causality. Unfortunately, causal delivery cannot be provided without costs: extra delays may be induced on message delivery or processes may be required to maintain and exchange records of causal relations. In this paper we present an extension to previous work on compression of causal information using knowledge about the topology of the communication structure. In order to make practical use of this result, we present a methodology to model the communication system. The technique exploits the physical structure of existing networks, in particular its hierarchical nature, to create a communication graph where causal separators match the underlying physical and administrative organization. We show that this approach can be applied to existing large-scale systems, providing the means for using topological timestamping with negligible overhead.
Rodrigues and Ver 'i ssimo reduced the timestamps cost in message passing systems using the information about the communication topology @cite_1 .