siiky
2023/03/13
2023/05/15
2023/05/15
course,distributed,programming
A program/system is linearizable if the results it produces could have been produced by a sequential program.
Serializability is a similar concept but applied to transactions (i.e. ordered sets of operations), taking each transaction as a single atomic operation.
A client wishing to read can read from a single replica. When wishing to write, it has to write to all replicas.
This is not fault-tolerant: a single replica goes down and clients can no longer write.
Subgroups of the all replicas are used to read and write.
The simplest approach is read/write to/from a majority of replicas. Depending on problem requirements, however, it may be more beneficial to unbalance the two subsets: in a read-heavy system, clients may read from fewer replicas, as long as they write to more replicas (there's a rule).
For this to work, the number of elements of the read/write quorums must meet a couple of requirements (N is number of replicas, Qr/Qw is the read/write quorum):
But... there's no definite order in which writes are applied: two given writes X=A and X=B may be applied in different orders in different replicas, so a client may read different values from different read quorums.
Or... because of network delays, even if operations are delivered and applied in different replicas in the same order, they may be delivered and applied in different times, so a client may read different values from different read quorums.
Algorithms of distributed consensus:
(Paxos) Leslie Lamport, "The Part-time Parliament"
(Paxos) Leslie Lamport, "Paxos Made Simple"
(HotStuff) "HotStuff: BFT Consensus in the Lens of Blockchain"
Basic Concepts and Taxonomy of Dependable and Secure Computing
What good are models and what models are good?