Week-3 Assignment 3
Solution
1. What is the primary goal of consensus algorithms in distributed systems?
a. To ensure all nodes agree on a single data value or decision.
b. To distribute load evenly across nodes.
c. To detect and recover from node failures.
d. To synchronize clocks across all nodes.
Ans: (a) To ensure all nodes agree on a single data value or decision.
The primary goal of consensus algorithms in distributed systems is- To ensure all nodes agree on a
single data value or decision.
Here's why this is the key function of consensus algorithms:
Distributed systems consist of multiple independent nodes (computers) working together.
These nodes may have different information or experiences due to network delays or partial views of
the system.
Consensus algorithms provide a mechanism for these nodes to communicate and reach an agreement
on a single value or decision. This ensures consistency across the system and prevents conflicting
actions.
While the other options are important aspects of distributed systems:
a. Synchronizing clocks is a related issue, but consensus algorithms specifically focus on
agreeing on data or decisions, not just time.
c. Distributing load evenly is achieved by load balancing techniques, not necessarily through
consensus algorithms.
d. Detecting and recovering from node failures can be facilitated by consensus algorithms
(e.g., electing a new leader node), but it's not the primary goal.
2. What does "agreement" refer to in the context of distributed systems?
a. Consensus among all processes in the system
b. Uniformity of data representation across nodes
c. Speed of message delivery
d. Synchronization of clocks
Ans: (a) Consensus among all processes in the system
In the context of distributed systems, "agreement" refers to: Consensus among all processes in the
system
Here's why this definition captures the essence of agreement:
• Distributed Nature: Distributed systems involve multiple processes running on separate
computers across a network. These processes may have access to different information or
experience events in a slightly different order.
• Common Goal: For the system to function correctly, there might be situations where
processes need to agree on a common value or state. This agreement ensures consistency
and prevents conflicting actions
3. True or False? In token-based algorithms, a unique token is shared among the sites. A site is
allowed to enter its critical section if it possesses the token.
a. True
b. False
Ans: (a) True
In token-based algorithms for mutual exclusion in distributed systems, a unique token is indeed shared
among all the sites. A site can only enter its critical section if it holds the token. This ensures that only
one site can be in its critical section at any given time, preventing conflicts and maintaining data
consistency.
4. In the context of rollback recovery, what is the "domino effect"?
a. Efficient message passing between nodes
b. Redundant checkpointing strategies
c. Automatic recovery without human intervention
d. Cascading failures caused by one node crashing
Ans: (d) Cascading failures caused by one node crashing
In the context of rollback recovery, the domino effect refers to: Cascading failures caused by one node
crashing
Here's why the domino effect can occur in rollback recovery:
• Dependencies Between Nodes: In distributed systems, processes often communicate and
exchange data. This creates dependencies between them.
• Rollback Triggers: When a failure occurs, and rollback recovery is initiated, the system might
need to roll back the state of a process to a previous checkpoint.
• Cascading Rollbacks: If the rolled-back process had sent messages or interacted with other
processes before the failure, those interactions might now be inconsistent with the rolled-back
state. This can trigger rollbacks in those dependent processes as well, creating a cascading
effect.
5. The Suzuki-Kasami broadcast algorithm is designed to handle:
a. Synchronous systems only
b. Asynchronous systems only
c. Both synchronous and asynchronous systems
d. Real-time systems exclusively
Ans: (c) Both synchronous and asynchronous systems
The Suzuki-Kasami broadcast algorithm's design, which does not rely on timing assumptions and
operates based on message exchanges and sequence numbers, makes it suitable for both synchronous
and asynchronous systems. It ensures mutual exclusion in a distributed environment regardless of the
underlying system's timing characteristics.
6. In Raymond's algorithm, the token is passed:
a. In a circular fashion
b. Along the edges of a logical tree
c. Randomly between processes
d. Only to the highest priority process
Ans: (b) Along the edges of a logical tree
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.
7. Which of the following techniques can help mitigate the livelock problem in checkpointing?
a. Increasing checkpoint frequency
b. Using optimistic concurrency control
c. Implementing coordinated checkpointing
d. Reducing system load
Ans: (c) Implementing coordinated checkpointing
• Livelock in checkpointing occurs when processes repeatedly roll back to the same checkpoint
without making progress. This can happen due to inconsistencies between checkpoints of
different processes.
• Coordinated checkpointing ensures that all participating processes take checkpoints
simultaneously or in a well-defined order. This helps to maintain consistency among
checkpoints and reduce the likelihood of livelock.
Other options:
• Increasing checkpoint frequency: While this might seem counterintuitive, it can actually
exacerbate the livelock problem as more frequent checkpoints can lead to more frequent
rollbacks.
• Using optimistic concurrency control: This technique is primarily used for concurrency
control, not specifically for addressing livelock in checkpointing.
• Reducing system load: While reducing system load can improve overall system performance,
it doesn't directly address the root cause of livelock.
By implementing coordinated checkpointing, the system can effectively prevent the cascading rollback
scenario that leads to livelock.
8. What does the Fischer-Lynch-Paterson (FLP) impossibility result state?
a. It is impossible to design a distributed algorithm for consensus in a synchronous system
b. It is impossible to reach consensus in an asynchronous system, even if a single process has
a crash failure
c. It is impossible to achieve consistency in a distributed database
d. It is impossible to design a distributed algorithm for leader election
Ans: (b) It is impossible to reach consensus in an asynchronous system, even if a single process has a
crash failure
The Fischer-Lynch-Paterson (FLP) impossibility result is a fundamental theorem in distributed
computing. It states that it is impossible to design a deterministic algorithm for reaching consensus in
an asynchronous system where even a single process might fail by crashing.
9. Cascaded rollback which causes the system to roll back to too far in the computation (even to the
beginning), in spite of all the checkpoints is known as:
a. Phantom Effect
b. Domino Effect
c. Rollback
d. Livelock
Ans: (b) Domino Effect
The domino effect accurately describes the cascading rollback that can occur in a distributed system,
where a single failure triggers a chain reaction of rollbacks, potentially leading to an excessive and
unnecessary rollback to a very early state.
10. What does each node maintain in the context of the HOLDER variables?
a. The number of privileges it holds
b. The status of other nodes in the network
c. The identity of a node that has the privilege or leads to the node having the privilege
d. The number of neighbors it has
Ans: (c) The identity of a node that has the privilege or leads to the node having the privilege
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.