Collaborative distributed applications trade off local responsiveness with global consistency. Optimistic replication favors responsiveness by assuming inconsistency won’t happen, or happens infrequently with modest consequences. The many projects involved with optimistic replication differ in how they mutate distributed state to provide infrequent, benign, and easily resolvable inconsistency.

A replicated abstract data type (RADT) is an ADT (an array, a linked list, or a hash table) extended so that mutating an RADT instance consistently mutates all instance copies. Storing distributed shared state in RADTs provides eventual consistency: if mutations in the application stop, the shared state eventually becomes consistent.

Mutations on an RADT are operation commutative, which allows noncausally related mutations to be executed in any order to the same effect. Each RADT instance uses precedence transitivity to order noncausal mutations, producing a result consistent with all other instance copies. The information exchanged among RADT instance copies is based on vector clocks modified to provide a scalable and reliable coordination protocol. Experiments with the linked list RADT show good performance, scalable with RADT size and count.

The paper is well written, although the coordination details get murky, as vector clock algorithms tend to do. The underlying theories are clearly motivated, and proofs are sketched with citations to further details. The implementation details are clear, and the reliability arguments are plausible; however, the failure assumptions could be more prominent. The bibliography is necessarily selective and appropriately up to date.