1) Define consistency [5]

A Consistency Model is a contract between the software and the memory. It states that the
memory will work correctly but only if the software obeys certain rules.
• The issue is how we can state rules that are not too restrictive but allow fast execution in
most common cases
• These models represent a more general view of sharing data than what we have seen so
far!
Consistency describes the relationships between items that are somehow connected. When
considering consistency of data, a consistent state requires that all relationships between data
items and replicas are as they should be i.e., that the data representation is correct. This focuses
on the correctness that can be seen in both the database as well as the distributed systems
community (but on different levels)
The term consistency is derived from the Latin word consistere which means \standing together"
or also \ stopping together". [Link]/.../Bermbach_netys2

2) Describe five consistency models [20]

i) Strict Consistency Model

Strict consistency model is the strongest form of memory coherence, having the most
stringent consistency requirements. A shared-memory system is said to support the strict
consistency model if the value returned by a read operation on a memory address is always the
same as the value written by the most recent write operation to that address, irrespective of the
locations of the processes performing the read and write operations. That is, all writes
instantaneously become visible to all processes."

ii) Sequential Consistency Model

It is one in which a multiprocessor is sequentially consistent if the result of the execution is
achievable by maintaining program order within a processor and interleaving accesses by
different processors in a random fashion.
The result of any execution is the same as if the (read and write) operations by all processes on
the data store were executed in some sequential order and the operations of each individual
process appear in this sequence in the order specified by its program.

Also the shared-memory supports the model if all processes see the same order of all memory
access operations on the shared memory.
Sequential consistency provides a simple and intuitive programming model while it disallows
many hardware and compiler optimizations that are possible in uniprocessors by enforcing a
strict order among shared memory operations.

iii) Casual Consistency Model

The causal consistency model weakens sequential consistency by requiring that only causally
related write operations are executed in the same order on all replicas.

It relaxes the requirement of the sequential model for better concurrency. Unlike the sequential
consistency model with causal consistency model, all processes see only those memory reference
operations in the same (correct) order that are potentially causally related. Memory reference
operations that are not potentially causally related may be seen by different processes in different
orders.

Two writes are causally related if the execution of one write possibly influences the value written
by the second write. If operations are not causally related they are said to be concurrent.
Concurrent writes can be executed in any order, as long as program order is respected.

iv) FIFO Consistency Model

Writes done by a single process are seen by all other processes in the order in which they were
issued, but writes from different processes may be seen in a different order by different
processes.
It is called PRAM consistency in the case of distributed shared memory systems.
The FIFO (or Pipelined RAM) consistency model, weakens causal consistency in that it removes
limitations about the order of any concurrent operations. FIFO consistency requires only that any
total ordering respect the program order (partial orderings of operations).

v) Weak Consistency Model

In this model critical sections are delimited using operations on synchronization variables (e.g.
locks). In this model performing a synchronize operation on a synchronization variable causes
the following to happen. First, all local writes are completed and the updated data items are
propagated to all other replicas. Second, all updates from other clients are executed locally (i.e.
the replica makes sure that its copy of the data is up-to-date). Essentially, weak consistency
imposes a sequentially consistent ordering of synchronized operations.

Shared data can be said to be consistent only after a synchronization is done. Before a
synchronization access can be performed, all previous regular data accesses must be completed.
This essentially leaves the problem of consistency up to the programmer. The memory will only
be consistent immediately after a synchronization operation.

3) Discuss the implementation of consistency models [15]

Coherence and Replication are very alike concepts that can deal with the same problem, but
Coherence is frequently used in hardware system for instance in Symmetric multiprocessing
Cache system where as Replication is often used in software systems taking for example in
distributed files systems and database systems. Coherence deals with data item at client side
and also with deals replicated data items that have corresponding ones in a reliable storage
backend, while Replication deals with data item at server side without dealing with replicated
data items.

Data Replication
To keep replicated data item consistent in distributed storage system, there are some essential
problems to think about that is where and how to store various replicas, what, when and how
to propagate update to replicas? Replica Server & Replica Content placement should be kept
as close to client as possible to improve performance and adjustment of replica placement is
 dynamically performed in accordance to access history. Issues with General Update
Propagation are what to, when to how to propagate?

Lastly Replication Protocols

A Replication protocol aims to implement some particular consistency model, the
features of the protocol are highly dependent on the target model. Implementation of
models that are popular in practical systems are addressed below.

Sequential Consistency
Primary Based Protocol - all write operations to a data item x is served by one special
replica called primary replica, this replica is responsible for updating other replicas, client
only interact with this special replica.

Replicated Write Protocol - write operations are sent to each replica to execute:
 Active Replication
The active replication protocol is a replicated write protocol. In this protocol write
operations are propagated to all replicas, while reads are performed locally. The writes
can be propagated using either point-to-point communication or multicast. The benefit
of this approach is that all replicas receive all operations at the same time (and in the
same order), and it is not necessary to track a primary, or send all operations to a
single server. However it does require atomic multicast or a centralized sequencer,
neither of which are scalable approaches.

 Quorum-Base Protocols
With quorum based protocols write operations are executed at a subset of all replicas.
When performing read operations clients must also contact a subset of replicas to find out
the newest version of the data. In this protocol all data items are associated with a version
number. Every time a data item is modified its version number is increased.
 This protocol defines a write quorum and a read quorum, which specify the number of
replicas that must be contacted for writes and reads respectively. The write quorum must
be greater than half of the total replicas, while the sum of the read quorum and the write
quorum must be greater than the total number of replicas. In this way a client performing
a read operation is guaranteed to contact at least one replica that has the newest version of
the data item. The choice of quorum sizes depends on the expected read-write ratio and
the cost of group communication.

 Eventual Consistency Protocol

Two requirements should be meet for this kind of protocol that is all update operations to
a data item should reach and be executed all replicas at same the time. These operations
should be executed in the same order. Some popular methods ensure these requirements
use write set and read set (use Nw, Nr to control how many processes should be involved
in write or read operation), thus how update operations are ordered. Expose data item
version number to client, so when client accesses data, it can pass known latest version
number to server to implement some client centric consistency model. Limit update
operation execution process, so write-write conflicts can be solved easily

Cache Coherence

Cache Coherence Protocol is used to keep client side replicas consistent in the context that a
reliable data item exists in storage backend (it's true for Symmetric multiprocessing cache like
hardware system and for distributed file system cache like software system).

Core problems of Cache Coherence Protocol:

 Coherence Detection Strategy
That is to say, when inconsistencies are actually detected. For example, in distributed
database system, this detection can be performed at the beginning of a transaction parallel
with the ongoing transaction but before it commits
 Coherence Enforcement Strategy
That is to say, how all caches are kept consistent with each other. Generally, there are
two methods. One is invalidating i.e.: if a data item is modified in one cache, other caches
that hold the same data item will receive an invalidation notification. The other is
propagating that is if a data item is modified in one cache, the update is propagated to
other caches that hold the same data item. So all replicas in cache are update to the same
version.

 Cache-Server Consistency
That is to say, how to keep data items in cache and in storage server consistent with each
other. There are several policies on how to use Read Only Cache, modification can only
be made on items in storage server, and cache pull these updates. Write Back,
modifications to data items are accumulated at cache side, and are written to storage
server at some other time. Write Through, modifications are made at cache, and are also
propagated to storage server. In SMP system, bus or directory may be used to serialize all
operations. While in distributed file systems, an exclusive lock may be needed for a data
cache that can perform modification operations to avoid write-write confliction.

 Implementing Cache Coherence

Implementation Mechanism
Directory Based - In a directory-based system, some information about the data being
shared is placed in a common directory. The directory acts as a filter through which the
processor must ask permission to load an entry from the primary memory to its cache.
When an entry is changed the directory either updates or invalidates the other caches with
that entry. It is not as fast as snooping but more scalable.

Snooping - In such system, the individual caches monitor address lines for accesses to
memory locations that they have cached. When a write operation is observed to a location
that a cache has a copy of, the cache controller invalidates or update its own copy of the
snooped memory location. Since it needs broadcasting, not very scalable.