Week-4 Assignment
Solution
1. What is the primary challenge in implementing Distributed Shared Memory (DSM) systems?
a. Achieving high-quality graphical rendering across nodes
b. Maintaining memory consistency among distributed processes
c. Synchronizing real-time audio processing
d. Designing a responsive user interface
Ans: (b) Maintaining memory consistency among distributed processes
Distributed Shared Memory (DSM) systems allow physically distributed computers to
share memory as if it were a single logical memory space.
2. In distributed systems, a minimum spanning tree (MST) is often constructed to optimize
network communication. One of its key applications is to efficiently support which of the
following communication patterns?
a. Unicasting
b. Anycasting
c. Multicasting
d. Broadcasting
Ans: (b) Broadcasting
Broadcasting:
• Broadcasting means sending a message from one node to all other nodes in the
system.
• Using an MST for broadcasting ensures that:
o All nodes receive the message, and
o It is done with minimal communication cost, avoiding redundant
transmissions and loops.
3. In Distributed Shared Memory (DSM) systems, which consistency model ensures that all
processes see memory operations (reads/writes) to the same memory location in the same order,
but not necessarily in real-time order?
a. Sequential Consistency
b. Causal Consistency
c. Eventual Consistency
d. Weak Consistency
Ans: (a) Sequential Consistency
• a. Sequential Consistency
Ensures all memory operations appear in some global order that is consistent
across all nodes.
Each process sees writes in the same order, though not necessarily the real-time
order.
• b. Causal Consistency
Ensures that causally related operations are seen in the same order by all nodes, but
concurrent (independent) writes may be seen in different orders.
• c. Eventual Consistency
Guarantees that if no new updates are made, all nodes will eventually see the same
values — but not immediately, and order can differ.
• d. Weak Consistency
Provides no guarantees about the order or visibility of memory operations unless
explicit synchronization is used
4. What challenges make it difficult to directly apply Prim's and Kruskal's algorithms for
finding a Minimum Spanning Tree (MST) in the message-passing model?
a. They are computationally complex.
b. They require knowing the state of the whole graph.
c. They involve multiple processes running in parallel.
d. They rely on global synchronization.
Ans: (b) They require knowing the state of the whole graph.
In the message-passing model (used in distributed systems):
• Prim's and Kruskal's algorithms assume access to global knowledge of the entire
graph (i.e., all vertices and edges).
• In a distributed system, each node (process) only knows about itself and its neighbors.
• Therefore, applying these algorithms directly is difficult because:
They require knowing the state of the whole graph, which is not available in a distributed,
message-passing environment.
5. Which issue is critical in the implementation of Distributed Shared Memory (DSM)?
a. Graphical rendering
b. Consistency maintenance
c. Audio processing
d. User interface design
Ans: (b) Consistency maintenance
In Distributed Shared Memory (DSM) systems, memory is logically shared but physically
distributed across different machines.
The critical issue is: Maintaining consistency across all nodes when multiple processes read
and write to shared memory.
This involves:
• Choosing and implementing a memory consistency model (e.g., sequential, causal,
eventual).
• Ensuring updates are seen in the correct order across all processes.
• Balancing performance vs correctness in synchronization and coherence.
6. Consider the following properties of a minimum spanning tree (MST):
MST Property 1: Given a fragment of an MST, let e be a minimum-weight outgoing edge of
the fragment. Then, joining e and its adjacent non-fragment node to the fragment yields another
fragment of an MST.
MST Property 2: If all the edges of a connected graph have the same weights, then the MST is
unique.
a. Both properties are true
b. Both properties are false
c. Only property 1 is true
d. Only property 2 is true
Ans: (c) Only property 1 is true
This is a well-known MST Greedy Property, also called the Cut Property:
If you have a fragment (partial tree) of an MST, and you select the minimum-weight edge that
crosses the cut between the fragment and the rest of the graph, then that edge is safe — it can
be added to form a larger fragment of the MST.
This is used in both Kruskal's and Prim's algorithms.
7. What is the main challenge in detecting deadlocks in distributed systems?
a. Lack of resources.
b. Synchronized clocks.
c. Lack of a global state.
d. Excessive memory usage.
Ans: (c) Lack of a global state.
Distributed systems, the main challenge in detecting deadlocks is:
Lack of a global state — there's no single point that can observe the entire system at once.
• Processes and resources are distributed across multiple machines.
• Each node has only partial knowledge of the system.
• Communication delays and asynchronous execution make it hard to reliably detect
cycles in wait-for graphs (WFGs), which are used to identify deadlocks.
8. Which graph structure is used for detecting deadlocks in distributed systems?
a. Spanning Tree
b. Wait-for Graph (WFG)
c. Directed Acyclic Graph (DAG)
d. Flowchart
Answer: b. Wait-for Graph (WFG)
A WFG shows which processes are waiting for which others; cycles in this graph indicate
deadlocks.
9. A cycle in a Wait-for Graph (WFG) indicates the presence of a deadlock in a distributed
system.
a. True
b. False
Ans: (a) True
In a Wait-for Graph, a cycle means that a set of processes are waiting on each other in a circular
chain, which is the defining condition for a deadlock.
10. Deadlock detection and recovery is the most suitable strategy for systems with high
availability requirements.
a. True
b. False
Ans: (a) True
In systems that prioritize high availability, it's important to keep the system running
continuously rather than blocking or rejecting resource requests in advance.
So, instead of preventing or avoiding deadlocks (which can reduce resource utilization), such
systems typically:
• Allow deadlocks to occur,
• Detect them when they happen, and
• Recover by terminating or rolling back some processes.
This ensures maximum resource usage and system responsiveness, aligning with high
availability goals.
