3 ms·

Doesn't strong consistency always imply some form of explicit locking that collides with availability? As in a distributed system it needs to go something like:

Doesn't strong consistency always imply some form of explicit locking that collides with availability? As in a distributed system it needs to go something like: 1. Get write request to a node 2. Node sends lock on that updated data to rest of nodes 3. After they send back OK the write happens 4. Propagate to rest of nodes 5. After receiving OK on the update from all of the nodes send notification to nodes to lift the lock So if a partition happens the system fails if it is CA while with e.g. CA it cannot guarantee strong consistency without resolving the split brain (killing of one of the partitions based on e.g. quorum)?

senderista 3y ago
If by "strong consistency" you mean "linearizability" then no, you can build a distributed atomic register without locking (ABD algorithm[0][1]). The trick is to force readers to complete a possibly-incomplete write returned from a read quorum by writing it to a write quorum before they can return their result (in practice you can elide the write-on-read in the common case where the result from the read quorum already is written to a write quorum). Similarly, writers must find the latest possibly-written version from a read quorum to obtain the version number for their write. If you need stronger primitives than atomic read/write (e.g. CAS), then ABD is insufficient and you need consensus in the asynchronous model (although synchronized clocks can allow even CAS to be implemented with ABD + leader election with leases[2]). [0] https://dl.acm.org/doi/pdf/10.1145/200836.200869 https://dl.acm.org/doi/pdf/10.1145/200836.200869 [1] https://www.cl.cam.ac.uk/teaching/2223/ConcDisSys/dist-sys-notes.pdf https://www.cl.cam.ac.uk/teaching/2223/ConcDisSys/dist-sys-n... [2] https://arxiv.org/pdf/1702.04242.pdf https://arxiv.org/pdf/1702.04242.pdf
dtornow 3y ago
My favorite mental framework to reason about consistency in distributed systems, Invariant Confluence, was formulated by Peter Bailis at al in Coordination Avoidance in Database Systems (overview and link to paper http://www.bailis.org/blog/when-does-consistency-require-coordination/ http://www.bailis.org/blog/when-does-consistency-require-coo...) Invariant confluence, determines whether an application requires coordination for correct execution. You can tailor the invariants to your requirements making invariant confluence a much better tool than CAP

senderista 3y ago

If by "strong consistency" you mean "linearizability" then no, you can build a distributed atomic register without locking (ABD algorithm[0][1]). The trick is to force readers to complete a possibly-incomplete write returned from a read quorum by writing it to a write quorum before they can return their result (in practice you can elide the write-on-read in the common case where the result from the read quorum already is written to a write quorum). Similarly, writers must find the latest possibly-written version from a read quorum to obtain the version number for their write. If you need stronger primitives than atomic read/write (e.g. CAS), then ABD is insufficient and you need consensus in the asynchronous model (although synchronized clocks can allow even CAS to be implemented with ABD + leader election with leases[2]). [0] https://dl.acm.org/doi/pdf/10.1145/200836.200869 https://dl.acm.org/doi/pdf/10.1145/200836.200869 [1] https://www.cl.cam.ac.uk/teaching/2223/ConcDisSys/dist-sys-notes.pdf https://www.cl.cam.ac.uk/teaching/2223/ConcDisSys/dist-sys-n... [2] https://arxiv.org/pdf/1702.04242.pdf https://arxiv.org/pdf/1702.04242.pdf

dtornow 3y ago

My favorite mental framework to reason about consistency in distributed systems, Invariant Confluence, was formulated by Peter Bailis at al in Coordination Avoidance in Database Systems (overview and link to paper http://www.bailis.org/blog/when-does-consistency-require-coordination/ http://www.bailis.org/blog/when-does-consistency-require-coo...) Invariant confluence, determines whether an application requires coordination for correct execution. You can tailor the invariants to your requirements making invariant confluence a much better tool than CAP