Consistency models are used in distributed systems to provide guarantees about the order and visibility of updates to shared data. Two commonly used consistency models are linearizability and serializability.
Linearizability is a consistency model that provides a strong guarantee of ordering and visibility of updates to shared data. It ensures that every read operation returns the result of the most recent write operation that completed before it, or an error if there is no such write. In other words, the system appears to each process as if all operations are executed atomically in a linear order, regardless of their physical execution order in the distributed system.
For example, suppose a distributed system maintains a counter that can be incremented by multiple processes simultaneously. If the system guarantees linearizability, then any read operation on the counter will always return the current value of the counter, even if the increments were executed concurrently across multiple nodes. This is because the linearizability consistency model ensures that the increment operations will appear to have occurred atomically in some linear order, regardless of the actual execution order.
Serializability is another consistency model that provides a weaker guarantee of ordering and visibility of updates to shared data than linearizability. It ensures that the outcome of any execution is equivalent to the outcome of a serial execution of all transactions, where each transaction executes atomically in its entirety before any other transaction starts. This means that the result of any concurrent execution is the same as if the transactions were executed in some sequential order.
For example, suppose a distributed system has two processes that each concurrently update a shared database. If the system guarantees serializability, then the resulting state of the database after the updates will be the same as if one of the processes executed first and then the other executed. This is because the serializability consistency model ensures that the concurrent updates will appear to have executed in some sequential order, regardless of their actual execution order.
In summary, linearizability and serializability are two commonly used consistency models in distributed systems. Linearizability provides a stronger guarantee of ordering and visibility of updates to shared data than serializability, but comes with higher overhead than serializability. Serializability provides a weaker guarantee of ordering and visibility of updates to shared data than linearizability, but with lower overhead. It is important for designers of distributed systems to choose the appropriate consistency model based on the requirements of their system.