3 ms·
The Herlihy-Wing paper defining linearizability is a good read https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf https://cs.brown.edu/~mph/HerlihyW90/p463-h
by oggy 7y ago
The Herlihy-Wing paper defining linearizability is a good read https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf and explains the difference with good examples, although it might be too mathy/formal for most people's taste. An interesting result in that paper is that the implementations of what Abadi calls isolation notions (which Herlihy and Wing call multi-object correctness criteria) are not modular - at least for (strict) serializability. For example, if two systems implement serializability using two-phase locking and multi-version concurrency control respectively, then they can't be modularly composed to get a serializable global system for transactions that span objects from both systems.