[wuch]

That is good point, so far I see one potential explanation, but it presumes that clients are on equal footing with other peers in the system. Whenever you send a write and destination discovers that it doesn't have all of writes operations this write depends on, you send them as well. On the other hand, if clients are tracking only dependencies without actual data behind them, then I don't see how to ensure availability - maybe with fixed entry point to the system (one for each client), but then it is not exactly available.

EDIT:

I did look at the actual paper [0], they provide a strong consistency within local data center, and a causal consistency with convergent conflict handling across data centers. They presume that each client resides within a data center, so it is essentially a variant of fixed entry point solution I mentioned earlier.

Additionally, what it quite important, you lose causal consistency if client connects to different data centers.

[0] Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS