5 ms·
The defininition from Herlihy and Wing (https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf), page 471.
by mjb 7y ago
The defininition from Herlihy and Wing (https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf), page 471. More informally, aphyr's definition from https://aphyr.com/posts/313-strong-consistency-models https://aphyr.com/posts/313-strong-consistency-models works well:
> each operation appears to take effect atomically at some point between its invocation and completion.
Here, operations are on single values (the paper calls them objects). So they are things like "add 1 to x" and not things like "read y and add its value to x".
- mehrdadn 7y agoIf that's what you mean then linearizable can't be the same as monotonic since monotonicity is weaker than sequential consistency, not stronger. If I understand LLVM's docs correctly, the difference between monotonicity and sequential consistency is that the former is for a single address whereas the latter is for all addresses. They would've been more clear on this if they had said "that the modification orders for different addresses can be combined to a global total order for the whole program".