CS3551 - DISTRIBUTED COMPUTING
III Year/V Semester QUESTION BANK
UNIT-IV
PART-A
1. Outline the issues in failure recovery. Apr/May 2024
Failure recovery in distributed systems presents several key challenges. These
include the complexity of coordinated checkpointing, the potential for domino effects
during recovery, and the overhead associated with maintaining and retrieving
consistent system states. Additionally, different types of failures (process, system,
storage, communication) require tailored recovery approaches.
2. State the use of Rollback recovery.
Restore the system back to a consistent state after a failure
a. Achieve fault tolerance by periodically saving the state of a process
during the failure-free execution.
b. Treats a distributed system application as communicate over a network.
3. what is checkpoint in recovery system and how it is used in distributed
computing
In a recovery system, a checkpoint is a saved state of a system that
allows it to be restored to a consistent point after a failure. In distributed computing,
checkpoints are crucial for fault tolerance, enabling systems to recover from process
or node failures by restarting from a previously saved state.
4. What do you mean by clock skew and clock drift? December 2022
Clock skew – Instantaneous difference between the readings of any two clocks is
called clock skew. Skew occurs since computer clocks like any others tends not be
perfect at all times.
5. Write the purpose of using checkpoints.
Check pointing is most typically used to provide fault tolerance to
applications. Check pointing techniques are useful not only for availability, but
also for program debugging, process migration, and load balancing.
6. What is the difference between agreement and consensus problem?
The difference between the agreement problem and the consensus problem is
that, in the agreement problem, a single process has the initial value, whereas in the
consensus problem, all processes have an initial value.
7. Define recovery.
Recovery refers to restoring a system to its normal operational state. Once a
failure has occurred, it is essential that the process where the failure happened
recover to a correct state. Fundamental to fault tolerance is the recovery from an
error.
8. Write short notes on strict two phase locking ? December 2022
A simple mechanism of a serializing mechanism is the use of exclusive locks.
Under a strict execution regime, a transaction that needs to read or write an object
must be delayed until other transactions that wrote the same object have committed or
aborted.
To enforce this rule, any locks applied during the progress of a transaction are held
until the transaction commits or aborts. This is called strict two-phase locking. The
presence of the locks prevents other transactions reading or writing the objects.
9. Explain two types of checkpoints.
Tentative: A temporary checkpoint that is made a permanent
checkpoint on the successful termination of the checkpoint algorithm.
Permanent: A local checkpoint at a process.
10. List drawback of synchronous check pointing.
a. Additional messages must be exchanged to coordinate check pointing
b. Synchronization delays are introduced during normal operations
c. No computational messages can be sent while the check pointing
algorithm is in progress.
d. If failure rarely occurs between successive checkpoints, then the
checkpoint algorithm places an unnecessary extra load on the system,
which can significantly affect performance.
11. How shadow versions are helpful in recovery?
Shadow version uses a map to locate versions of the server's objects in a file
called a version store. The map associates the identifiers of the server's objects
with the positions of their current versions in the version store. The versions
written by each transaction are shadows of the previous committed versions. The
transaction status entries and intentions lists are stored separately. When a
transaction commits, a new map is made by copying the old map and entering the
positions of the shadow versions. To complete the commit process, the new map
replaces the old map.
12. Define fault and failure. What are different approaches to fault-tolerance?
Fault: Anomalous physical condition, eg design errors, manufacturing
problems, damage, external disturbances.
Failure of a system occurs when the system does not perform its service in
the manner specified.
13.List the requirements of consensus algorithm to hold for execution.
The requirements of consensus algorithm to hold for execution are
1. Termination
2. Agreement and
3. Integrity.
14.What are the performance aspects of agreement protocols? Following metrics
are used
1. Time: No of rounds needed to reach an agreement.
2. Message traffic: Number of messages exchanged to reach an
agreement.
3. Storage overhead: Amount of information that needs to stored at
processors during execution of the protocol.
15.What are the application of agreement algorithm? Applications of agreement
algorithms
a. Fault-tolerant clock synchronization.
b. Distributed systems require physical clocks to synchronized
c. Physical clocks have drift problem.
d. Agreement protocols may help to reach a common clock value. •
Synchronizing distributed clocks:
e. At any time, values of clocks of all non-faulty processes must be
approximately equal.
f.There is a small bound on amount by which the clock of a non-faulty process
is changed during re-synchronization.
16.State Byzantine agreement problem.
In the Byzantine agreement problem, n processors communicate with each
other in order to reach an agreement on a binary value b. There are bad processors.
that may collaborate with each other in order to prevent an admissible agreement.
Each processor has an initial binary value. The agreement must reflect to a certain
extent the majority among the initial value.
17.What is local checkpoints?
A process may take a local check point anytime during the execution. The
local checkpoints of different processes are not coordinated to form a global
consistent checkpoint.
18.What is forced checkpoints?
To guard against the domino effect, a communication induced checkpoint
protocol piggybacks protocol-speci?c information to application messages that
processes exchange. Each process examines the information and occasionally is
forced to take a checkpoint according to the protocol.
19.Explain useless checkpoints.
A useless checkpoint of a process is one that will never be part of a global
consistent state. Useless checkpoints are not desirable because they do not
contribute to the recovery of the system from failures, but they consume resources
and cause performance overhead.
20. What is checkpoint intervals?
A checkpoint interval is the sequence of events between two consecutive
checkpoints in the execution of a process.
21. Is the basic idea behind task assignment approach? Basic idea:
a. A process has already been split up into pieces called tasks:
b. The amount of computation required by each task and they are known.
c. The cost of processing each task on every node is known.
d. The IPC costs between every pair of tasks are known.
e. Precedence relationships among the tasks are known.
f. Reassignment of tasks is not possible. Mention some motivations for
replication.
PART - B
1. Explain the Solution to Byzantine Agreement Problem.
2. Illustrate briefly the two kinds of checkpoints for checkpoint algorithm? Dec 2022
3. Discuss the issues of failure recovery with an example? May 2022
4. Illustrate the different types of failure in distributed systems? May 2022
5. Explain in detailed consensus algorithm for Byzantine failures? Nov/Dec 2024
6. Write a detailed the various storage service in cloud computing? Nov/Dec 2024
7. Explain facts associated with agreement in failure-free system of both synchronous
and asynchronous systems Nov/Dec 2023
8. What is agreement free system? Explain how agreement is reached in message-
passing synchronous system with failures. Apr/May 2024
9. Discuss about the Checkpoint – Based Recovery. Explain the coordinated.
Check pointing algorithm with illustration. Nov/Dec 2023
10. Detail how you would implement checkpointing and rollback recovery so that any
crash of up to two nodes can be recovered with no loss of committed state
Include labeled sequence diagrams for coordination and global rollback.
