A method for verifying a consistency level in a key-value store, in which a value is stored in a cloud-based storage system comprising a read/write register identified by a key. At a centralized monitor node, a history of operations including writes and reads performed at the key is created, and a distance between a read of a value at the key and a latest write to the key is determined. It can then be ascertained whether the distance satisfies a relaxed atomicity property.