News for hackers. Stuff that matters.
Re:The CAP theorem. The Bad, the Bad, & the Ugly by senderista on Friday March 08, 2024 @11:36AM (#39642749)
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

[1] https://www.cl.cam.ac.uk/teaching/2223/ConcDisSys/dist-sys-n...

[2] https://arxiv.org/pdf/1702.04242.pdf

There are no comments on this comment yet.