Abstract. This paper explores causally consistent distributed services when multiple related services are replicated to meet performance and availability requirements. This consistency criterion is particularly well suited for distributed services such as cooperative document sharing, and it is attractive because of the efficient implementations that are allowed by it. A new protocol for implementing causally consistent services is presented. It allows service instances to be created and deleted dynamically according to service access patterns in the distributed system. It also handles the case where different but related services are replicated independently. Another novel aspect of this protocol lies in its ability to use both push and pull mechanisms for disseminating updates to objects that encapsulate service state.

Print publication: Issue 2 (June 1999)
Received 10 June 1998