Week 3
1.In a Classical Algorithm of Ring Election, what will be the message complexity for N
labelled processes.
A. (N-1) messages
B. (2N-1) messages
C. (3N-1) messages
D. (4N-1) messages
Answer: C. (3N-1) messages
Explanation:
● The Chang-Roberts leader election algorithm in a unidirectional ring has a
worst-case message complexity of (3N-1).
● N messages are used for the leader ID passing, another N messages for
comparisons, and (N-1) messages for the final leader announcement.
● Total: (3N - 1) messages.
2.True or False ?
There is no leader election algorithm for anonymous rings, even if algorithm knows the
ring size (non-uniform) and synchronous model.
A. True
B. False
Answer: A. True
Explanation:
● In anonymous rings, all nodes are indistinguishable (no unique IDs).
● Even if the ring size is known, there is no deterministic way to elect a leader
without breaking symmetry.
● Without additional mechanisms (e.g., randomization or external identifiers),
leader election is impossible.
3.True or False ?
Zookeeper is a replicated service that holds the metadata of distributed applications.
A. True
B. False
Answer: A. True
Explanation:
● ZooKeeper provides distributed coordination, configuration management, and
metadata storage for distributed applications.
● It ensures fault tolerance by replicating data across multiple nodes.
4.True or False ?
“Leader Election problem represents a general class of non symmetry-breaking
problems.”
A. True
B. False
Answer: B. False
Explanation:
● Leader election is a symmetry-breaking problem because its goal is to select a
single leader among multiple identical nodes.
● In anonymous rings, symmetry cannot be broken deterministically, making leader
election impossible without additional mechanisms.
5.ZooKeeper itself is intended to be replicated over a sets of hosts called :
A. Chunks
B. Ensemble
C. Subdomains
D. None of the mentioned
Answer: B. Ensemble
Explanation:
● ZooKeeper operates with a group of replicated servers known as an "ensemble".
● A quorum (majority of nodes) must agree to ensure consistency and fault
tolerance.
6.Find the message and time complexity of below algorithm:
send value of own id to the left
when receive an id j (from the right):
if j > id then
forward j to the left (this processor has lost)
if j = id then
elect self (this processor has won)
if j < id then
do nothing
2
A. O(𝑛 ) Messages and O(n) time
B. O(logn) Messages and O(logn) time
2
C. O(n) Messages and O(𝑛 ) time
3
D. O(𝑛 ) Messages and O(n) time
Answer: A. O(n²) Messages and O(n) Time
Explanation:
● Each ID must travel across the ring, leading to a worst-case O(n²) messages.
● Since each node only forwards IDs in one direction, the time complexity is O(n).
7.In the O(nlogn) messages leader election algorithm, the probe distance in phase k is
_______ and the Number of messages initiated by a processor in phase k is at most
______________including probes and replies in both directions.
𝑘−1 𝑘
A. 2 ,4
𝑘
B. 2𝑘, 4∗2
𝑘
C. k, 2
𝑘 𝑘
D. 2 , 4∗2
𝑘 𝑘
Answer: D. 2 , 4∗2
Explanation:
𝑘
● Phase k probes a distance of 2 .
𝑘
● Each processor sends at most 4∗2 messages in the worst case (probes and
replies).
8.Consider the following statements:
Statement 1: When two processes are competing with each other causing data
corruption, it is called deadlock
Statement 2: When two processes are waiting for each other directly or indirectly, it is
called race condition.
A. Only statement 1 is true
B. Only statement 2 is true
C. Both statements are true
D. Both statements are false
Answer: D. Both statements are false
Explanation:
● Deadlock occurs when processes wait for resources indefinitely. (Not data
corruption).
● Race condition happens when two processes access shared data
simultaneously, leading to corruption.
● The definitions are incorrectly swapped.
9.In an anonymous ring topology, which of the following is true regarding leader
election?
A. Leader election is always possible in both synchronous and asynchronous
settings
B. Leader election is possible only if the number of nodes is known.
C. Leader election is impossible in an anonymous ring without additional
mechanisms.
D. The election can be performed using a random number assigned to each node.
Answer: C. Leader election is impossible in an anonymous ring without additional
mechanisms.
Explanation:
● Anonymous rings lack unique identifiers, so all nodes appear the same.
● Without extra mechanisms (like unique IDs or randomization), leader election is
impossible due to symmetry.
10.How does having unique node identifiers (non-uniform ring) affect the leader election
process?
A. It makes the election process more complex and inefficient.
B. It allows leader election to be completed in a finite number of steps using
identifier-based comparison.
C. It has no impact, as the algorithm would work the same way in uniform and
non-uniform rings.
D. It requires additional communication rounds to resolve conflicts among nodes
Answer: B. It allows leader election to be completed in a finite number of steps using
identifier-based comparison.
Explanation:
● Unique IDs break symmetry, making leader election feasible.
● Algorithms like Chang-Roberts or Hirschberg-Sinclair use identifier comparisons
to elect a leader in finite steps.
