CAP, ACID, BASE
Consistency
モバイル通信プロトコル授業資料
Werner Vogels
Relationships
Linearizability
Linearizability for read and write operations is synonymous with the term “atomic consistency” and is the "C" of the CAP Theorem
Linearizability is composable (or “local”) because, if operations on each object in a system are linearizable, then all operations in the system are linearizable.
Serializability
Serializability is the traditional “I,” or isolation, in ACID
If users’ transactions each preserve application correctness (“C,” or consistency, in ACID), a serializable execution also preserves correctness. Therefore, serializability is a mechanism for guaranteeing database correctness.
Unlike linearizability, serializability does not—by itself—impose any real-time constraints on the ordering of transactions.
Serializability is also not composable.
Serializability does not imply any kind of deterministic order—it simply requires that some equivalent serial execution exists.
FLP
MICHAEL J. FISCHER, NANCY A. LYNCH, MICHAEL S. PATERSON
Consensus, FLP, and Paxos Slide by Wyatt Lloyd @Princeton From intuitive explanation of FLP to Paxos
So FLP, with its strictly weaker restrictions - all messages are eventually delivered, faulty nodes don’t have to achieve consensus - is by this definition a stronger result than CAP, which allows messages to be lost forever and forces partitioned nodes to participate in the system.
CAP Theorem
Eric A. Brewer @PODC'00
Seth Gilbert, Nancy Lynch
ACM SIGACT'02
Definitons of C, A and P
1. Atomic Data Objects (Atomic, or linearizable, consistency)
There must exist a total order on all operations such that each operation looks as if it were completed at a single instant
2. Available Data Objects
Every request received by a non-failing node in the system must result in a response
3. Partition Tolerance
Allowed to lose arbitrarily many messages sent from one node to another