[IgorPartola]

In that case, if client A wants to do something with the value x, it should instruct the server to place metadata on it, essentially saying that it's reading it with the intent to update. This could be implemented as "update x with value of get(x)". That way it would be placed into pending with metadata.

Having a heartbeat between the client and the server could also help prevent the write from getting purged from "pending" prematurely.

[pbailis]

I'll also add that the metadata requirements aren't huge--typically 8 bytes for the timestamp and N*(bytes per key) for the keys. In our implementation and the benchmarks that we provided, we don't garbage collect the metadata as it's small and isn't a serious overhead.