Week -3 Assignment
Solution
1. In transaction processing systems, ____________ phenomenon occurs when a
cascading rollback forces the system to revert excessively far back in the computation -
potentially even to the beginning - despite the presence of checkpoints?
a. Phantom Effect
b. Domino Effect
c. Simple Rollback
d. Livelock
Ans: (b) Domino Effect
In transaction processing systems, the Domino Effect refers to a situation where a failure
or rollback in one transaction causes a chain reaction of rollbacks in other dependent
transactions. This can lead the system to roll back all the way to the beginning, even if
checkpoints were present, but not effectively isolating the states.
• Phantom Effect relates to phantom reads in database isolation.
• Simple Rollback is a generic rollback of a transaction.
• Livelock is a concurrency issue where processes keep changing state but don’t make
progress.
2. Which problem do consensus algorithms fundamentally solve in distributed systems?
a. Clock synchronization between nodes
b. Achieving agreement on a value/decision despite failures
c. Load balancing across server nodes
d. Failure detection and recovery
Ans: (b) Achieving agreement on a value/decision despite failures
Consensus algorithms (like Paxos, Raft, or PBFT) are designed to solve the fundamental
problem of getting multiple nodes in a distributed system to agree on a single value (e.g.,
committing a transaction or deciding on the next leader), even when some nodes may fail or
act maliciously (in Byzantine scenarios).
3. True/False? In the context of rollback recovery, Cascading failures caused by one node
crashing is not represented by the "domino effect"?
a. True
b. False
Ans: (b) False
In rollback recovery, cascading failures—where the failure of one node leads to dependent
rollbacks in other nodes—are exactly what the "domino effect" represents.
The Domino Effect occurs when:
• A single process rolls back to a previous checkpoint due to a failure.
• Other processes that communicated with it must also roll back to maintain
consistency.
• This can continue backward through the system, potentially forcing a rollback to the
very beginning of the computation, even if checkpoints were made.
4. Which property is NOT required by the Consensus Problem?
a. Agreement on a single value
b. Termination within bounded time
c. Validity if all non-faulty processes propose the same value
d. Tolerance to Byzantine (arbitrary) failures
Ans: (d) Tolerance to Byzantine (arbitrary) failures
The Consensus Problem (in its basic form) requires the following core properties:
1. Agreement: All correct (non-faulty) processes must agree on the same value.
2. Termination: All correct processes must eventually decide on a value.
3. Validity: If all correct processes propose the same value, then any correct process that
decides must decide on that value.
5. Which property ensures that all non-faulty nodes in a distributed system eventually
agree on the same value?
a. Availability
b. Partition tolerance
c. Termination
d. Agreement
Ans: (d) Agreement
In the context of distributed consensus, the property that ensures all non-faulty nodes
eventually agree on the same value is Agreement
6. What is the primary goal of checkpointing in distributed systems?
a. To synchronize clocks across all nodes
b. To ensure data consistency
c. To minimize network latency
d. To recover from failures efficiently
Ans: (d) To recover from failures efficiently
Checkpointing is a fault-tolerance technique in distributed systems where the system
periodically saves the state of processes. In the event of a failure, the system can roll back to
a previously saved state (checkpoint), rather than restarting from scratch.
7. Which rollback recovery scheme periodically saves the system state to stable storage?
a. Checkpoint-based recovery schemes
b. Log-based recovery schemes
c. Hybrid recovery schemes
d. Real-time recovery schemes
Ans: (a) Checkpoint-based recovery schemes
Checkpoint-based recovery schemes work by periodically saving the state of the system
or process to stable storage. When a failure occurs, the system can roll back to the last saved
checkpoint, avoiding the need to start from the very beginning.
8. True/False? In the context of the HOLDER variable in distributed mutual exclusion,
each node maintains the identity of the node that currently holds the privilege or leads to
it.
a. True
b. False
Ans: (a) True
Each node in Raymond's Tree-based algorithm maintains a HOLDER variable which stores the
identity of another node. This node is believed to either possess the privilege or is on the path
to obtaining the privilege. This information helps nodes to forward requests for the privilege
towards the node that currently holds it or is in the process of acquiring it. Sources and related
content.
9. Which metric is used to evaluate the performance of rollback recovery schemes?
a. Disk space utilization
b. Message delivery latency
c. Recovery time
d. Network bandwidth
Ans: (c) Recovery time
In rollback recovery schemes, the primary goal is to recover from failures efficiently.
Therefore, the key metric used to evaluate their performance is Recovery time.
10. True/ False? Raymond's algorithm, the token is not passed along the edges of a logical
tree.
a. True
b. False
Ans: (b) False
Raymond's algorithm employs a tree-based structure to manage the token passing process. The
processes in the distributed system are organized into a logical tree. When a process acquires
the token, it passes it to one of its children in the tree. This ensures that the token is eventually
passed to all processes in the system, preventing deadlock and starvation.
Key points:
• Logical tree: The processes are arranged in a hierarchical structure.
• Token passing: The token moves from parent to child nodes in the tree.
• Distributed nature: The algorithm operates without a central coordinator. By using a
tree-based approach, Raymond's algorithm effectively manages the token and ensures
fair access to the critical section for all processes in the distributed system
