Student No.:
DSA5208: Scalable Distributed Computing for Data Science
Quiz
20 June 2024
Time allowed: 60 minutes
INSTRUCTIONS
1. Please write your student number on the cover page.
2. This quiz contains TEN questions and comprises FIVE pages.
3. Answer ALL questions.
4. This is an OPEN BOOK quiz. But electronic devices are NOT allowed.
5. There may be more than one correct answer for mutiple choice questions. Select all
correct answers.
1
Q1 (8 marks) Consider the following distributed diagram:
(i) Write down all events that happen before e61:
(ii) Write down all events exi that satisfy e
x
i ∥ e21:
Q2 (4 marks) The diagram in Q1 is an example of .
(A) the FIFO model
(B) the CO model
(C) none of the above
Q3 (12 marks) Assume that each event takes one logic time unit to complete. Then in
the diagram of Q1,
(i) the scalar time of event e61 is .
(ii) the vector time of event e61 is .
(iii) if the Singhal-Kshemkalyani’s differential technique is applied to maintain the
vector clock, the array LS3 is after the event e
6
3.
Q4 (8 marks) Consider the following diagram with five broadcast messages:
where the events that broadcast messages are labelled in red for clarity. This
diagram is an example of .
(A) FIFO broadcast
(B) causal broadcast
2
(C) FIFO-total order broadcast
(D) none of the above
Q5 (20 marks) Consider the synchronous Bellman-Ford algorithm for the following
diagram (p1 is the root):
Write down the shortest distance from p1 to all other pi:
• p1 → p2:
• p1 → p3:
• p1 → p4:
• p1 → p5:
In this algorithm, how many messages are sent/received in total?
Q6 (8 marks) Assume that the α synchronizer is implemented in the following network.
The diagram also labels the regular messages sent and received in a round. Use
arrows to draw other messages (including “ack” & “safe”) that are sent and received
in the implementation of the α synchronizer. Use dashed arrows for “ack” messages
and solid arrows for “safe” messages.
message
3
Q7 (8 marks) The following invocation/response diagram satisfies .
(A) strict consistency
(B) sequential consistency
(C) causal consistency
(D) none of the above
Q8 (12 marks) Consider the following invocation/response diagram:
(i) If the diagram satisfies strict consistency, all possible values of “?” are
(ii) If the diagram satisfies sequential consistency, all possible values of “?” are
(iii) If the diagram satisfies causal consistency, all possible values of “?” are
Q9 (8 marks) In the following diagram, is violated.
4
(A) Read-your-writes consistency
(B) Monotonic-reads consistency
(C) Monotonic-writes consistency
(D) none of the above
Q10 (12 marks) The following diagram shows how the Brent-Kung algorithm is applied
to find the prefix sum of the sequence 2, 9, 3, 4, 6, 1:
18
25
14 24
2 9 3 4 6 1
11 7 7
Draw a similar diagram to show how the Kogge-Stone algorithm is applied to find
the prefix sum of the sequence 1, 3, 2, 4, 8, 1, 4.
5

学霸联盟