Discussion about this post

User's avatar
suman suhag's avatar

The original proof only requires that when there are overlapping reads and write to the same storage, only the the write must be correct, for the algorithm to function properly.

And yes, it assumes that there is cache coherence among all actors, and therefore that the writes will be idempotent across all nodes — which in fact is what guarantees coherency.

The algorithm was developed for cache coherent MESI coherence model systems, or better.

So no, it does not include clusters, or distributed systems, unless they also guarantee operational idempotence.

For databases in particular, including the subset of instances of database implementations we callā€filesystemsā€, that the overall system provides ACI(F)D guarantees.

Databases which only supply BASE, like NoSQL implementations, need not apply.

Or in other words, don’t expect Lamport’s to work on those systems, and pick a different algorithm instead,because in the context of the proof onthose systems, the proof no longer is a proof.

Expand full comment

No posts