CST 402 - DISTRIBUTED

COMPUTING
 Module –IV
Distributed shared memory and Failure
Recovery
 Module –IV
Lesson Plan
● L1: Distributed shared memory –Abstraction and advantages
● L2: Shared memory mutual exclusion –Lamport’s bakery algorithm
● L3: Checkpointing and rollback recovery –System model, consistent and
inconsistent states
● L4: different types of messages, Issues in failure recovery.
● L5: checkpoint based recovery
● L6: log based roll back recovery
 Distributed shared memory –Abstraction and advantages

● Distributed shared memory (DSM) is an abstraction provided to the

programmer of a distributed system.
● It gives the impression of a single monolithic memory, as in traditional von
Neumann architecture
● Programmers access the data across the network using only read and write
primitives
● Programmers do not have to deal with send and receive communication
primitives and the ensuing complexity of dealing explicitly with
synchronization and consistency in the message passing model.
● A part of each computer’s memory is earmarked for shared space, and the
remainder is private memory
 Distributed shared memory –Abstraction and advantages

● To provide programmers with the illusion of a single shared address space, a

memory mapping management layer is required to manage the shared virtual
memory space.
 Distributed shared memory –Abstraction and advantages

DSM has the following advantages:

● 1. Communication across the network is achieved by the read/write
abstraction that simplifies the task of programmers.
● 2. A single address space is provided, thereby providing the possibility of
avoiding data movement across multiple address spaces, and simplifying
passing- by- reference and passing complex data structures containing
pointers.
● 3. If a block of data needs to be moved, the system can exploit locality of
reference to reduce the communication overhead.
● 4. DSM is often cheaper than using dedicated multiprocessor systems, because
it uses simpler software interfaces and off- the- shelf hardware.
● 5. There is no bottleneck presented by a single memory access bus
 Distributed shared memory –Abstraction and advantages

● 6. DSM effectively provides a large (virtual) main memory.

● 7. DSM provides portability of programs written using DSM. This portability
arises due to a common DSM programming interface, which is independent of
the operating system and other low- level system characteristics.
 Distributed shared memory –Abstraction and advantages

DSM has the following disadvantages:

1. Programmers are not shielded from having to know about various replica
consistency models and from coding their distributed applications according
to the semantics of these models.
2. As DSM is implemented under the covers using asynchronous message
passing, the overheads incurred are at least as high as those of a message
passing implementation. As such, DSM implementations cannot be more
effi cient than asynchronous message- passing implementations. The generality
of the DSM software may make it less effi cient.
3. By yielding control to the DSM memory management layer, programmers lose
the ability to use their own message- passing solutions for accessing shared
objects. It is likely that the standard implementations of DSM have a higher
overhead than a programmer- written implementation tailored for a specific
application and system
 Distributed shared memory –Abstraction and advantages

The main issues in designing a DSM system are the following:

• Determining what semantics to allow for concurrent access to shared objects.
The semantics needs to be clearly specified so that the programmer can code his
program using an appropriate logic.

• Determining the best way to implement the semantics of concurrent access to

shared data. One possibility is to use replication. One decision to be made is the
degree of replication –partial replication at some sites, or full replication at all
the sites. A further decision then is to decide on whether to use read- replication
(replication for the read operations) or write- replication (replication for the write
operations) or both.

• Selecting the locations for replication (if full replication is not used), to
 Distributed shared memory –Abstraction and advantages

• Determining the location of remote data that the application needs to access, if
full replication is not used.
• Reducing communication delays and the number of messages that are involved
under the covers while implementing the semantics of concurrent access to
shared data.
 Shared memory mutual exclusion

■ Operating systems have traditionally dealt with multi- process synchronization

using algorithms based on first principles, high- level constructs such as
semaphores and monitors,

■ These algorithms are applicable to all shared memory systems

■ the bakery algorithm, which requires O (n) accesses in the entry section,
irrespective of the level of contention
■ fast mutual exclusion, which requires O (1) accesses in the entry section in the
absence of contention.

■ Bakery algorithm also illustrates an interesting technique in resolving

concurrency
 Lamport’s bakery algorithm
■ Lamport proposed the classical bakery algorithm for n- process mutual
exclusion in shared memory systems
■ The algorithm is so called because it mimics the actions that customers follow
in a bakery store.
■ A process wanting to enter the critical section picks a token number that is
one greater than the elements in the array
■ Processes enter the critical section in the increasing order of the token
numbers.
■ In case of concurrent accesses to choosing by multiple processes, the
processes may have the same token number.
■ In this case, a unique lexicographic order is defined on the tuple < token , pid>,
and this dictates the order in which processes enter the critical section
■ The algorithm can be shown to satisfy the three requirements of the critical
section problem: (i) mutual exclusion, (ii) bounded waiting, and (iii) progress.
 Lamport’s bakery algorithm
■ In the entry section, a process chooses a timestamp for itself, and resets it to 0
in the exit section.

■ In lines 1a–1c each process chooses a timestamp for itself, as the max of the
latest timestamps of all processes, plus one

■ These steps are non- atomic; thus multiple processes could be choosing
timestamps in overlapping durations.
 Lamport’s bakery algorithm
■ In the entry section, a process chooses a timestamp for itself, and resets it to 0
in the exit section.

■ each process chooses a timestamp for itself, as the max of the latest
timestamps of all processes, plus one

■ These steps are non- atomic; thus multiple processes could be choosing
timestamps in overlapping durations.
Lamport’s bakery algorithm
 Checkpointing and rollback recovery

■ Rollback recovery treats a distributed system application as a collection of

processes that communicate over a network.
■ It achieves fault tolerance by periodically saving the state of a process during
the failure- free execution, enabling it to restart from a saved state upon a
failure to reduce the amount of lost work.
■ The saved state is called a checkpoint, and the procedure of restarting from a
previously checkpointed state is called rollback recovery.
■ In distributed systems, rollback recovery is complicated because messages
induce inter- process dependencies during failure- free operation.
■ Upon a failure of one or more processes in a system, these dependencies may
force some of the processes that did not fail to roll back, creating what is
commonly called a rollback propagation
 Checkpointing and rollback recovery

■ To see why rollback propagation occurs, consider the situation where the
sender of a message m rolls back to a state that precedes the sending of m.

■ The receiver of m must also roll back to a state that precedes m’s receipt;

■ otherwise, the states of the two processes would be inconsistent because they
would show that message m was received without being sent, which is
impossible in any correct failure- free execution.

■ This phenomenon of cascaded rollback is called the domino effect.

■ In a distributed system, if each participating process takes its checkpoints

independently, then the system is susceptible to the domino effect.
 Checkpointing and rollback recovery
■ This approach is called independent or uncoordinated checkpointing.

■ It is obviously desirable to avoid the domino effect and therefore several

techniques have been developed to prevent it.

■ One such technique is coordinated checkpointing where processes coordinate

their checkpoints to form a system- wide consistent state.
■ In case of a process failure, the system state can be restored to such a
consistent set of checkpoints, preventing the rollback propagation.
■ Alternatively, communication- induced checkpointing forces each process to
take checkpoints based on information piggybacked on the application
messages it receives from other processes.
■ Checkpoints are taken such that a system- wide consistent state always exists
on stable storage, thereby avoiding the domino effect
 Checkpointing and rollback recovery

■ Logbased rollback recovery combines checkpointing with logging of

nondeterministic events.
■ Log- based rollback recovery relies on the piecewise deterministic (PWD)
assumption, which postulates that all non- deterministic events that a process
executes can be identified and that the information necessary to replay each
event during recovery can be logged in the event’s determinant.
■ By logging and replaying the non- deterministic events in their exact original
order, a process can deterministically recreate its pre- failure state even if this
state has not been checkpointed.
■ Log- based rollback recovery in general enables a system to recover beyond
the most recent set of consistent checkpoints.
 Checkpointing and rollback recovery

System model
A distributed system consists of a fixed number of processes, P1, P2… PN , which
communicate only through messages.

Processes cooperate to execute a distributed application and interact with the

outside world by receiving and sending input and output messages, respectively
 Checkpointing and rollback recovery
System model
■ Rollback- recovery protocols generally make assumptions about the reliability
of the inter- process communication.

■ Some protocols assume that the communication subsystem delivers messages

reliably, in first- in- first- out (FIFO) order, while other protocols assume that the
communication subsystem can lose, duplicate, or reorder messages.

■ The choice between these two assumptions usually affects the complexity of
checkpointing and failure recovery.

■ a system recovers correctly if its internal state is consistent with the

observable behavior of the system before the failure
 Checkpointing and rollback recovery
System model
■ Rollback- recovery protocols therefore must maintain information about the
internal interactions among processes and also the external interactions with
the outside world.
A local checkpoint
■ In distributed systems, all processes save their local states at certain instants
of time.

■ This saved state is known as a local checkpoint.

■ A local checkpoint is a snapshot of the state of the process at a given instance

and the event of recording the state of a process is called local checkpointing.

■ The contents of a checkpoint depend upon the application context and the
checkpointing method being used.
 Checkpointing and rollback recovery
System model
Depending upon the checkpointing method used, a process may keep several
local checkpoints or just a single checkpoint at any time.

We assume that a process stores all local checkpoints on the stable storage so
that they are available even if the process crashes.

We also assume that a process is able to roll back to any of its existing local
checkpoints and thus restore to and restart from the corresponding state

A local checkpoint is shown in the process- line by the symbol “ | ”.

 Checkpointing and rollback recovery
consistent and inconsistent states
A global state of a distributed system is a collection of the individual states of all
participating processes and the states of the communication channels.

Intuitively, a consistent global state is one that may occur during a failure- free
execution of a distributed computation.

More precisely, a consistent system state is one in which a process’s state reflects
a message receipt, then the state of the corresponding sender must reflect the
sending of that message
 Checkpointing and rollback recovery

The state in Figure 13.2(a) is consistent and the state in Figure 13.2(b) is
inconsistent.

Note that the consistent state in Figure 13.2(a) shows message m1 to have been
sent but not yet received, but that is alright.

The state in Figure 13.2(a) is consistent because it represents a situation in which

every message that has been received, there is a corresponding message send
 Checkpointing and rollback recovery
The state in Figure 13.2(b) is inconsistent because process P2 is shown to have
received m2 but the state of process P1 does not reflect having sent it. Such a
state is impossible in any failure- free, correct computation.

Inconsistent states occur because of failures. For instance, the situation shown in
Figure 13.2(b) may occur if process P1 fails after sending message m2 to process
P2 and then restarts at the state shown in Figure 13.2(b).

Thus, a local checkpoint is a snapshot of a local state of a process and a global

checkpoint is a set of local checkpoints, one from each process.

A consistent global checkpoint is a global checkpoint such that no message is

sent by a process after taking its local checkpoint that is received by another
process before taking its local checkpoint
 Checkpointing and rollback recovery
■ The consistency of global checkpoints strongly depends on the flow of
messages exchanged by processes and an arbitrary set of local checkpoints at
processes may not form a consistent global checkpoint

■ The fundamental goal of any rollback- recovery protocol is to bring the system
to a consistent state after a failure.

■ The reconstructed consistent state is not necessarily one that occurred before
the failure.

■ It is suffi cient that the reconstructed state be one that could have occurred
before the failure in a failure- free execution, provided that it is consistent with
the interactions that the system had with the outside world.
 Different types of messages
A process failure and subsequent recovery may leave messages that were
perfectly received (and processed) before the failure in abnormal states.

This is because a rollback of processes for recovery may have to rollback the send
and receive operations of several messages
 Different types of messages
1. In- transit messages
■ In Figure the global state shows that message m1 has been sent but not yet
received. We call such a message an in- transit message

■ When in- transit messages are part of a global system state, these messages do
not cause any inconsistency.

■ However, depending on whether the system model assumes reliable

communication channels, rollback- recovery protocols may have to guarantee
the delivery of in- transit messages when failures occur.
■ For reliable communication channels, a consistent state must include in- transit
messages because they will always be delivered to their destinations in any
legal execution of the system.
 Different types of messages
■ On the other hand, if a system model assumes lossy communication channels,
then in- transit messages can be omitted from system state.
2. Lost messages
■ Messages whose send is not undone but receive is undone due to rollback are
called lost messages.

■ This type of messages occurs when the process rolls back to a checkpoint prior
to reception of the message while the sender does not rollback beyond the
send operation of the message.

■ In Figure 13.3, message m1 is a lost message.

 Different types of messages
3. Delayed messages
■ Messages whose receive is not recorded because the receiving process was
either down or the message arrived after the rollback of the receiving process,
are called delayed messages.
■ For example, messages m2 and m5 in Figure 13.3 are delayed messages.

4. Orphan messages
■ Messages with receive recorded but message send not recorded are called
orphan messages.
■ For example, a rollback might have undone the send of such messages, leaving
the receive event intact at the receiving process.
■ Orphan messages do not arise if processes roll back to a consistent global
state.
 Different types of messages
5. Duplicate messages
Duplicate messages arise due to message logging and replaying during process
recovery
 Issues in failure recovery
In a failure recovery, we must not only restore the system to a consistent state,
but also appropriately handle messages that are left in an abnormal state due to
the failure and recovery
 Issues in failure recovery
■ The computation comprises of three processes Pi, Pj, and Pk, connected
through a communication network.

■ The processes communicate solely by exchanging messages over fault- free,

FIFO communication channels.

■ Processes Pi, Pj, and Pk have taken checkpoints {Ci0, Ci1}, {Cj0, Cj1, Cj2}, and
{Ck0, Ck1}, respectively, and these processes have exchanged messages A to J

■ Suppose process Pi fails at the instance indicated in the figure.

■ All the contents of the volatile memory of Pi are lost and, after Pi has
recovered from the failure, the system needs to be restored to a consistent
global state from where the processes can resume their execution.

■ Process Pi’s state is restored to a valid state by rolling it back to its most recent
checkpoint Ci1.
 Issues in failure recovery
■ To restore the system to a consistent state, the process Pj rolls back to
checkpoint Cj1 because the rollback of process Pi to checkpoint Ci1 created an
orphan message H

■ Note that process Pj does not roll back to checkpoint Cj2 but to checkpoint
Cj1, because rolling back to checkpoint Cj2 does not eliminate the orphan
message H.

■ Even this resulting state is not a consistent global state, as an orphan message
I is created due to the roll back of process Pj to checkpoint Cj1.

■ To eliminate this orphan message, process Pk rolls back to checkpoint Ck1.

■ The restored global state {Ci1, Cj1, Ck1} is a consistent state as it is free from
orphan message

■ Although the system state has been restored to a consistent state, several
messages are left in an erroneous state which must be handled correctly.
 Issues in failure recovery
■ Messages A, B, D, G, H, I, and J had been received at the points indicated in the
figure and messages C, E, and F were in transit when the failure occurred.

■ Restoration of system state to checkpoints {Ci1, Cj1,Ck1} automatically

handles messages A, B, and J because the send and receive events of
messages A, B, and J have been recorded, and both the events for G, H, and I
have been completely undone.

■ These messages cause no problem and we call messages A, B, and J normal

messages and messages G, H, and I vanished messages

■ Messages C, D, E, and F are potentially problematic.

■ Message C is in transit during the failure and it is a delayed message.

■ The delayed message C has several possibilities: C might arrive at process Pi

before it recovers, it might arrive while Pi is recovering, or it might arrive after
Pi has completed recovery.
■ Each of these cases must be dealt with correctly.
 Issues in failure recovery
■ Message D is a lost message since the send event for D is recorded in the
restored state for process Pj, but the receive event has been undone at process
Pi.

■ Process Pj will not resend D without an additional mechanism, since the send D
at Pj occurred before the checkpoint and the communication system
successfully delivered D

■ Messages E and F are delayed orphan messages and pose perhaps the most
serious problem of all the messages.

■ When messages E and F arrive at their respective destinations, they must be

discarded since their send events have been undone.

■ Processes, after resuming execution from their checkpoints, will generate both
of these messages, and recovery techniques must be able to distinguish
between messages like C and those like E and F.
 Issues in failure recovery
■ Lost messages like D can be handled by having processes keep a message log
of all the sent messages.
■ So when a process restores to a checkpoint, it replays the messages from its
log to handle the lost message problem.
■ However, message logging and message replaying during recovery can result
in duplicate messages
 Checkpoint Based Recovery
■ In the checkpoint- based recovery approach, the state of each process and the
communication channel is checkpointed frequently so that, upon a failure, the
system can be restored to a globally consistent set of checkpoints

■ less restrictive and simpler to implement than log- based rollback recovery.

■ However, checkpoint- based rollback recovery does not guarantee that

prefailure execution can be deterministically regenerated after a rollback.

■ Therefore, checkpoint- based rollback recovery may not be suitable for

applications that require frequent interactions with the outside world.

■ Checkpoint- based rollback- recovery techniques can be classified into three

categories:

■ uncoordinated checkpointing,
■ coordinated checkpointing,
■ communication- induced checkpointing
 Checkpoint Based Recovery
uncoordinated checkpointing,

■ In uncoordinated checkpointing, each process has autonomy in deciding when

to take checkpoints.

■ This eliminates the synchronization overhead as there is no need for

coordination between processes and it allows processes to take checkpoints
when it is most convenient or effi cient.

■ The main advantage is the lower runtime overhead during normal execution,
because no coordination among processes is necessary.

■ Autonomy in taking checkpoints also allows each process to select appropriate

checkpoints positions.

■ However, uncoordinated check pointing has several shortcomings

 Checkpoint Based Recovery
■ First, there is the possibility of the domino effect during a recovery, which may
cause the loss of a large amount of useful work.

■ Second, recovery from a failure is slow because processes need to iterate to

find a consistent set of checkpoints

■ Since no coordination is done at the time the checkpoint is taken, checkpoints

taken by a process may be useless checkpoints

■ Useless checkpoints are undesirable because they incur overhead and do not
contribute to advancing the recovery line

■ Third, uncoordinated checkpointing forces each process to maintain multiple

checkpoints

■ Fourth, it is not suitable for applications with frequent output commits

because these require global coordination to compute the recovery line,
 Checkpoint Based Recovery
■ As each process takes checkpoints independently, we need to determine a
consistent global checkpoint to rollback to, when a failure occurs.

■ In order to determine a consistent global checkpoint during recovery, the

processes record the dependencies among their checkpoints caused by
message exchange during failure- free operation.

■ When a failure occurs, the recovering process initiates rollback by broadcasting

a dependency request message to collect all the dependency information
maintained by each process.

■ When a process receives this message, it stops its execution and replies with
the dependency information saved on the stable storage as well as with the
dependency information

■ The initiator then calculates the recovery line based on the global dependency
information and broadcasts a rollback request message containing the
recovery line.
 Checkpoint Based Recovery
2. Coordinated checkpointing

In coordinated checkpointing, processes orchestrate their checkpointing

activities so that all local checkpoints form a consistent global state

Coordinated checkpointing simplifies recovery and is not susceptible to the

domino effect, since every process always restarts from its most recent
checkpoint.

Also, coordinated checkpointing requires each process to maintain only one

checkpoint on the stable storage,

The main disadvantage of this method is that large latency is involved in

committing output,
 Checkpoint Based Recovery
2. Coordinated checkpointing

Blocking coordinated checkpointing

A straightforward approach to coordinated checkpointing is to block

communications while the checkpointing protocol executes.

After a process takes a local checkpoint, to prevent orphan messages, it remains

blocked until the entire checkpointing activity is complete.

The coordinator takes a checkpoint and broadcasts a request message to all

processes, asking them to take a checkpoint.

When a process receives this message, it stops its execution, flushes all the
communication channels, takes a tentative checkpoint, and sends an
acknowledgment message back to the coordinator.
 Checkpoint Based Recovery
2. Coordinated checkpointing

Non- blocking checkpoint coordination

In this approach the processes need not stop their execution while taking
checkpoints.

A fundamental problem in coordinated checkpointing is to prevent a process

from receiving application messages that could make the checkpoint inconsistent.

Coordinated checkpointing requires all processes to participate in every

checkpoint.

This requirement generates valid concerns about its scalability.

It is desirable to reduce the number of processes involved in a coordinated

checkpointing session.

This can be done since only those processes that have communicated with the
checkpoint initiator either directly or indirectly since the last checkpoint need to
 Checkpoint Based Recovery
2. Coordinated checkpointing

Communication- Induced checkpointing

Communication- induced checkpointing is another way to avoid the domino

effect, while allowing processes to take some of their checkpoints independently.

Processes may be forced to take additional checkpoints and thus process

independence is constrained to guarantee the eventual progress of the recovery
line.

Communication- induced checkpointing reduces or completely eliminates the

useless checkpoints.

In communication- induced checkpointing, processes take two types of

checkpoints, namely, autonomous and forced checkpoints

The checkpoints that a process takes independently are called local checkpoints,
while those that a process is forced to take are called forced checkpoints
 Checkpoint Based Recovery
2. Coordinated checkpointing

Communication- Induced checkpointing

There are two types of communication- induced checkpointing
1. modelbased checkpointing
2. index- based checkpointing.

In model- based checkpointing, the system maintains checkpoints and

communication structures that prevent the domino effect or achieve some even
stronger properties.

In index- based checkpointing, the system uses an indexing scheme for the local
and forced checkpoints, such that the checkpoints of the same index at all
processes form a consistent state.
 Log- based rollback recovery
■ A log- based rollback recovery makes use of deterministic and
nondeterministic events in a computation

Deterministic and non- deterministic events

Log- based rollback recovery exploits the fact that a process execution can be
modeled as a sequence of deterministic state intervals, each starting with the
execution of a non- deterministic event.

A non- deterministic event can be the receipt of a message from another process
or an event internal to the process.

For example, in Figure the execution of process P0 is a sequence of four

deterministic intervals.

The first one starts with the creation of the process, while the remaining three
start with the receipt of messages m0, m3, and m7, respectively.
 Log- based rollback recovery

■ Send event of message m2 is uniquely determined by the initial state of P0 and

by the receipt of message m0, and is therefore not a non- deterministic event.

■ Log- based rollback recovery assumes that all non- deterministic events can be
identified and their corresponding determinants can be logged into the stable
storage.

■ During failure- free operation, each process logs the determinants of all non-
deterministic events that it observes onto the stable storage.
 Log- based rollback recovery
■ Additionally, each process also takes checkpoints to reduce the extent of
rollback during recovery.
■ After a failure occurs, the failed processes recover by using the checkpoints
and logged determinants to replay the corresponding non- deterministic
events precisely as they occurred during the pre- failure execution.
■ Because execution within each deterministic interval depends only on the
sequence of non- deterministic events that preceded the interval’s beginning,
■ The no- orphans consistency condition

■ Let e be a non- deterministic event that occurs at process p. We define the

following

■ Depend(e): the set of processes that are affected by a non- deterministic event
e. This set consists of p, and any process whose state depends on the event e
according to Lamport’s happened before relation

■ Log(e): the set of processes that have logged a copy of e’s determinant in their
volatile memory.
 Log- based rollback recovery
■ Stable(e): a predicate that is true if e’s determinant is logged on the stable
storage.

■ This property is called the always- no- orphans condition

■ Log- based rollback- recovery protocols guarantee that upon recovery of all
failed processes, the system does not contain any orphan process,

Log- based rollback- recovery protocols are of three types:

1. pessimistic logging,

2. optimistic logging,

3. causal logging
 Log- based rollback recovery
1. Pessimistic logging

■ Pessimistic logging protocols assume that a failure can occur after any non-
deterministic event in the computation.

■ This assumption is “pessimistic” since in reality failures are rare

■ In their most straightforward form, pessimistic protocols log to the stable

storage the determinant of each non- deterministic event before the event
affects the computation.

■ Pessimistic protocols implement the following property, often referred to as

synchronous logging, which is a stronger than the always- no- orphans
condition
 Log- based rollback recovery
1. Pessimistic logging

■ That is, if an event has not been logged on the stable storage, then no process
can depend on it.

■ In addition to logging determinants, processes also take periodic checkpoints

to minimize the amount of work that has to be repeated during recovery.

■ When a process fails, the process is restarted from the most recent checkpoint
and the logged determinants are used to recreate the prefailure execution.

■ in Figure During failure- free operation the logs of processes P0, P1, and P2
contain the determinants needed to replay messages m0, m4, m7, m1, m3, m6,
and m2, m5, respectively.

■ Suppose processes P1 and P2 fail as shown, restart from checkpoints B and C,

and roll forward using their determinant logs to deliver again the same
sequence of messages as in the pre- failure execution.
 Log- based rollback recovery
1. Pessimistic logging

■ This guarantees that P1 and P2 will repeat exactly their pre- failure execution
and re- send the same messages.

■ Hence, once the recovery is complete, both processes will be consistent with
the state of P0 that includes the receipt of message m7 from P1.

■ In a pessimistic logging system, the observable state of each process is always

recoverable.
 Log- based rollback recovery
1. Pessimistic logging

■ fast non- volatile semiconductor memory can be used to implement the stable
storage.

■ Another approach is to limit the number of failures that can be tolerated.

■ The overhead of pessimistic logging is reduced by delivering a message or

executing an event and deferring its logging until the process communicates
with another process or with the outside world.

■ Some pessimistic logging systems reduce the overhead of synchronous

logging without relying on hardware.

■ For example, the sender- based message logging (SBML) protocol keeps the
determinants corresponding to the delivery of each message m in the volatile
memory of its sender.
 Log- based rollback recovery
2. Optimistic logging
■ In optimistic logging protocols, processes log determinants asynchronously to
the stable storage .

■ These protocols optimistically assume that logging will be complete before a

failure occurs.

■ Determinants are kept in a volatile log, and are periodically flushed to the
stable storage.

■ Optimistic logging protocols do not implement the always- no- orphans

condition.

■ The protocols allow the temporary creation of orphan processes which are
eventually eliminated.

■ To perform rollbacks correctly, optimistic logging protocols track causal

dependencies during failure free execution.
■ Upon a failure, the dependency information is used to calculate and recover
the latest global state of the pre- failure execution in which no process is in an
 Log- based rollback recovery
3. Causal logging

Causal logging combines the advantages of both pessimistic and optimistic

logging at the expense of a more complex recovery protocol

Like optimistic logging, it does not require synchronous access to the stable
storage except during output commit.

Like pessimistic logging, it allows each process to commit output independently

and never creates orphans, thus isolating processes from the effects of failures at
other processes.

Moreover, causal logging limits the rollback of any failed process to the most
recent checkpoint on the stable storage, thus minimizing the storage overhead
and the amount of lost work.

Causal logging protocols make sure that the always- no- orphans property holds
by ensuring that the determinant of each non- deterministic event that causally
precedes the state of a process is either stable or it is available locally to that
process.
 Log- based rollback recovery
3. Causal logging

Process P0 at state X will have logged the determinants of the nondeterministic

events that causally precede its state according to Lamport’s happened- before
relation.

These events consist of the delivery of messages m0, m1, m2, m3, and m4.

The determinant of each of these non- deterministic events is either logged on

the stable storage or is available in the volatile log of process P0.
 Log- based rollback recovery
3. Causal logging

The determinant of each of these events contains the order in which its original
receiver delivered the corresponding message.

The message sender, as in sender- based message logging, logs the message
content. Thus, process P0 will be able to “guide” the recovery of P1 and P2