Distributed Computing
Consistency
and Replication
Computer Engineering Dept.
VESIT
Nupur Giri
Strict Consistency
Any read on a data item x returns a value corresponding to the results
of the most recent write on x
Behavior of two processes, operating on the same data item.
• A strictly consistent store.
• A store that is not strictly consistent.
Linearizability Consistency (2)
The result of any execution is the same as if the read and the 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.
In addition, if ts OP1(x) < ts OP2(y), then operation OP1(x) should
Precede OP(y) in this sequence.
Causal Consistency (1)
Necessary condition:
Writes that are potentially casually related must
be seen by all processes in the same order.
Concurrent writes may be seen in a different
order on different machines.
Causal Consistency (2)
This sequence is allowed with a causally-consistent store, but
not with sequentially or strictly consistent store.
Sequential Consistency (1/single copy)
The result of any execution is the same as if the read and the 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.
a) A sequentially consistent data store.
b) A data store that is not sequentially consistent.
Causal Consistency (3)
a) A violation of a casually-consistent store.
b) A correct sequence of events in a casually-consistent store.
FIFO Consistency (1) Pipelined RAM
Necessary Condition:
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.
FIFO Consistency (2)
A valid sequence of events of FIFO consistency
Weak Consistency (1)
Properties:
• Accesses to synchronization variables associated with a data
store are sequentially consistent.
(All processes see all ops on synch. Variable in the same process in the same order.)
• No operation on a synchronization variable is allowed to be
performed until all previous writes have been completed
everywhere.
(Syn. Forces all writes that are in progress or partially completed at some local copies but
not others to complete everywhere.)
• No read or write operation on data items are allowed to be
performed until all previous operations to synchronization
variables have been performed.
(when a data item is accessed either for reading or for writing all the syncs. have to be
completed )
Weak Consistency (2)
a) A valid sequence of events for weak
consistency.
b) An invalid sequence for weak consistency.
Release Consistency (1)
A valid event sequence for release consistency.
Release Consistency (2)
Rules:
• Before a read or write operation on shared data
is performed, all previous acquires done by the
process must have completed successfully.
• Before a release is allowed to be performed, all
previous reads and writes by the process must
have completed
• Accesses to synchronization variables are FIFO
consistent (sequential consistency is not
required).
Entry Consistency (1)
Conditions:
• An acquire access of a synchronization variable is not allowed
to perform with respect to a process until all updates to the
guarded shared data have been performed with respect to that
process.( At an acquire, all remote changes to the guarded data must be made
visible)
• Before an exclusive mode access to a synchronization variable
by a process is allowed to perform with respect to that process,
no other process may hold the synchronization variable, not
even in nonexclusive mode. (the process should enter critical region and
ensure mutual exclusion)
• After an exclusive mode access to a synchronization variable
has been performed, any other process's next nonexclusive
mode access to that synchronization variable may not be
performed until it has performed with respect to that variable's
owner. (the process entering CR in non exclusive mode should check with the
owner of the variable if the copy is most recent)
Entry Consistency (1)
A valid event sequence for entry consistency.
Summary of Data Centric - Consistency Models
Consistency Description
Strict Absolute time ordering of all shared accesses matters.
All processes must see all shared accesses in the same order. Accesses are
Linearizability
furthermore ordered according to a (nonunique) global timestamp
All processes see all shared accesses in the same order. Accesses are not ordered in
Sequential
time
Causal All processes see causally-related shared accesses in the same order.
All processes see writes from each other in the order they were used. Writes from
FIFO
different processes may not always be seen in that order
(a)
Consistency Description
Weak Shared data can be counted on to be consistent only after a synchronization is done
Release Shared data are made consistent when a critical region is exited
Entry Shared data pertaining to a critical region are made consistent when a critical region is
entered.
(b)
a) Consistency models not using synchronization operations.
b) Models with synchronization operations.
Monotonic Reads
If a process reads the value of a data item x, any successive read
operation on x by that process will always return that same value
or a more recent value. ie. If a process has seen a value of x at
time t , it will never see an older version of x at a later time.
The read operations performed by a single process P at two
different local copies of the same data store.
a) A monotonic-read consistent data store
b) A data store that does not provide monotonic reads.
Real-World Examples of Monotonic Reads Consistency
● Cassandra: Implementation: Cassandra, a distributed NoSQL database, offers tunable consistency levels,
including options that can ensure monotonic reads through mechanisms like read repair and lightweight
transactions. Social media platforms where user activity feeds need to reflect the latest interactions
without showing older states.
● Amazon DynamoDB: DynamoDB provides eventual consistency by default but can be configured for
stronger consistency models, including monotonic reads using conditional writes and consistent reads. E-
commerce platforms where inventory data must consistently reflect the latest stock levels to avoid
overselling.
● Google Cloud Spanner: Cloud Spanner offers strong consistency guarantees, including monotonic reads,
by using synchronized clocks (TrueTime) to order transactions. Financial applications where transaction
histories must reflect a consistent and non-decreasing order of operations.
● Apache HBase: HBase, a distributed database that runs on top of the Hadoop ecosystem, uses
timestamps to ensure that clients always read the most recent data available. Real-time analytics systems
where time-series data must reflect a consistent progression of events.
Monotonic Writes
Any write can be performed on adata item if all copies have been
made up to date with the preceding write on the same data store.
ie. Write operation by the process P on a data item is X is
completed before any successive write operation on X by Same
Process.
The write operations performed by a single process P at two different local
copies of the same data store
a) A monotonic-write consistent data store.
b) A data store that does not provide monotonic-write consistency.
Real-World Examples of Monotonic Writes Consistency
Monotonic Writes Consistency plays a critical role in real-world systems.
● E-commerce Transactions: Online shopping platforms use Monotonic Writes Consistency to maintain order
accuracy. When customers place orders, it ensures that stock updates and payment processes occur in the
correct sequence, preventing issues like double-selling or stock discrepancies.
● Banking Systems: Banks employ this consistency model to process transactions sequentially. This prevents
errors such as account overdrafts or incorrect balance reporting, which can occur if withdrawals and
deposits are not processed in the order they were initiated.
● Cloud Storage Services: Services like Google Drive and Dropbox ensure file updates are applied in the
order they are received. This consistency is crucial when multiple users are editing a document
simultaneously, ensuring that all changes are reflected correctly and no data is lost or overwritten.
● IoT Device Management: In IoT networks, Monotonic Writes Consistency helps manage signals from
numerous devices efficiently. This ensures that commands sent to devices are executed in the correct order,
vital for maintaining system stability and functionality.
Read Your Writes
The effect of a write operation by a process on data item x will
always be seen by a successive read operation on x by the same
process.
a) A data store that provides read-your-writes consistency.
b) A data store that does not.
1. Social Media Platforms:
● Scenario: A user posts a new status update or comment.
● Importance: The user should immediately see their new post or comment in their feed to confirm the action
was successful.
● Implementation: The system routes the user's read requests to the same replica or master node that
processed the write.
2. Online Banking Applications:
● Scenario: A user transfers money from their savings to their checking account.
● Importance: The user should see the updated balance reflecting the transfer immediately to trust the
system's accuracy.
● Implementation: The banking system ensures the user's read requests for account balances are handled by
the node where the write occurred.
3. E-commerce Websites:
● Scenario: A user adds items to their shopping cart.
● Importance: The user should see the added items in their cart right away to proceed with the purchase.
● Implementation: The e-commerce platform directs the user's reads to the master database or ensures the
replication delay is minimal.
Writes Follow Reads
A write operation by a process on a data item x following a previous
read operation on x by the same process , is guaranteed to take place on
the same or a more recent value of x that was read.
a) A writes-follow-reads consistent data store
b) A data store that does not provide writes-follow-reads consistency
It assures that reactions to articles are stored at a local copy only if the original is
stored there as well.
Scenarios Illustrating Read-your-Writes
1. Collaborative Document Editing:
● Scenario: Multiple users are editing a document simultaneously. When a user makes a change, they should
see their edits immediately.
● Implementation: The system can achieve this by having each user’s reads directed to the master database
or ensuring that their changes are prioritized in replication to the nodes they are reading from.
2. User Profile Updates:
● Scenario: A user updates their profile information, such as their email address or profile picture.
● Importance: The user should see the updated information immediately to confirm the changes.
● Implementation: The application can route the user's read requests to the master database until the
changes propagate to replicas.
3. Messaging Applications:
● Scenario: A user sends a message in a chat application.
● Importance: The user should see the sent message in the chat history immediately.
● Implementation: The messaging system can store the message in a master database and immediately
show it in the user’s chat history view.
Fault Tolerance
▪ OS
Crash deadlock
o client-server connection
failure,
o listen thread is not available
o buffer size is not adequate
• send buffer overflows
• even link failure
⮚ Providing data too soon or
late
❑ Black hole routers
Failure Detection: Synchronous /Asynchronous
Failure Masking
•
• 1. Information redundancy:, parity, checksums, Hamming codes, forward error
correction (FEC) codes, etc.
• 2. Time redundancy: An additional time that is used to deliver the service of a
system or multiple executions of an operation. For example, retransmission
handling in networks, or if a transaction aborts, then rollback till the closest
checkpoint restarts.
• 3. Physical redundancy For example, extra processes can be added to a system
so that if a small number of them get crashed, the system can still function
correctly.
Even in biology (mammals have two eyes, two ears, two lungs, etc.), aircraft
(747s have four engines but can fly on three), and sports (multiple referees in
case one misses an event). Another example is Hadoop Distributed File
System (HDFS)
Byzantine agreement problem
(Byzantine Generals Problem)
Assumptions and Goals:
●Assume that processes are synchronous, messages are unicast while preserving
ordering, and communication delay is bounded.
●Assume N processes, where each process i will provide a value vi to others.
●Goal- Let each process construct a vector V of length N, such that
○ if process i is non-faulty, V [i] = vi
○ ELSE V [i] is undefined/unknown
●Assume that there are at most k faulty processes.
(a) Each process sends its value to others
(b) The vectors, that each process assembles,
The generals announce their troop strengths (for example, in units
of 1-k soldiers) to the other members of a group by sending a
message.
[Link] vectors V, that each general assembles, are based on (a),
each general knows its own strength. They then send their vectors
to all the other generals.
[Link] general receives vectors in step 3. It is clear to all that
General 3 is the traitor. In each ‘column’, the majority value is
assumed to be correct.
RPC Call Semantics in the Presence
of Failure
Consistent Cut: Global state
The two main forms of recovery are as follows:
· Backward Recovery: In backward recovery, the main issue is to bring a system
from its present erroneous state back into a previously correct state.
For example, in a reliable communication through packet retransmission in effect,
it means that you attempt to go back to a previous correct state, namely the
one in which the packet that was lost is being fetched again.
Checkpoint and message logging (can be very expensive, especially when errors
are very rare) are the methods that are used for backward recovery. But it is not
always possible. Some states can simply never be rolled back. Despite the cost,
backward recovery is implemented more often. The “logging” of information can be
thought of as a type of checkpointing.
· Forward Recovery: In this case, when a system has entered an erroneous
state, instead of moving back to a previously checkpointed state, bring the
system in a correct new state from which it can continue to execute. For
example, a missing packet is constructed from other, successfully delivered
packets using error-correcting coding techniques.
Consistent Cut: Global state
Recording and restarting from a checkpoint in a distributed system are a bit more complex.
In the case of a message-passing system, if each node independently records a periodic
local checkpoint, an inconsistent global state may be recorded.
For example, after recovery, it can appear as though a message is sent but is never
received or that a message is received but is never sent.
Dominos Effect : Orphan management
Dominos Effect Implementation
● The domino effect can also be avoided with uncoordinated checkpoints by
logging all messages between processes.
● During recovery, messages are replayed from the message logs until the log is
exhausted.
● However, the overhead of saving all previous checkpoints and all messages is
undesirable due to the volume of information recorded and is impractical for
embedded systems with limited resources.
● Although types of Pessimistic logging, Optimistic logging and Causal
logging limit and structure the types of logs being created and try to reduce the
overhead