Relaxed consistency requirements for replicated objects

Shared objects are usually replicated in a distributed environment for higher availability and fault tolerance. Coherent or strongly consistent implementation of replicated objects have been studied extensively in the literature. This paper concentrates on a general method for specifying and implementing replicated objects that only require weaker consistency conditions. The weakness of the objects is left open and users are allowed to specify their objects by defining how concurrent sets of operations should be performed. The implementation of a replicated object consists of two modules: one module is an algorithm to identify concurrent sets from a distributed computation, and the other module is a user defined procedure to process the concurrent sets. We show examples of weaker objects that can be defined and implemented efficiently because of the less stringent requirements imposed on these objects. In particular, the ordered set dictionary problem is used to demonstrate our scheme and we show that non-blocking implementation of the dictionary is possible