The model for cache coherency is eventual consistency. Caches may be inconsistent at any one moment, but all caches converge to the same state over time. If all users stop generating updates all replicas will reach a consistent state by applying the same updates.
Logical clocks are used to preserve causal ordering of updates as described in [11]. Logical clocks are incremented when new updates are timestamped and to synchronize with other servers. Relay servers use the logical clocks to timestamp new updates as they are received from client applications. A single server timestamps updates to the same object according to the order updates are received from clients. Updates to the same object from different server nodes are given a timestamp by their respective ``accepting'' server with understanding that logical clocks are loosely synchronized. To synchronize the logical clocks, servers use the timestamps of incoming updates as a lower bound for their own clock. Therefore if any update arrives with a timestamp greater than the server's logical clock, the server must adjust its clock to be at least the value of the timestamp.
Eventual consistency is achieved by guaranteeing that only the latest updates are applied to objects. Each update encapsulates the entire state of an object. An update is applied if and only if its timestamp is newer than that of the last update applied to the same object. Updates with older timestamps are discarded. In the case where two updates to the same object have the same timestamp, a deterministic tie-breaker algorithm based on server numbers chooses which update is applied.
Caches converge to equivalent final states even when updates arrive out of order. This is because each update contains enough information to supersede and replace previous versions of the updated object. However, a consequence of out of order delivery of updates is that intermediate states may not be consistent across all clients, possibly resulting in unobserved updates. This may not be acceptable for all collaborative applications. The Relay system is designed for DCAs that can tolerate unobserved updates and inconsistent intermediate states.