Birla Institute of Technology &
Science, Pilani
Work-Integrated Learning Programmes
Division
Second Semester 2017-2018
Comprehensive Examination
(EC-3 Regular)
Course No. :
SS ZG526
Course Title : DISTRIBUTED COMPUTING
Nature of Exam : Open
Book
Weightage :
45%
Duration : 3 Hours
Date of Exam :
21/04/2018 (AN)
Note:
1.
Please follow all the Instructions to Candidates given on the
cover page of the answer book.
2.
All parts of a question should be
answered consecutively. Each answer should start from a fresh page.
3.
Assumptions made if any, should be
stated clearly at the beginning of your answer.
Q.1 (a) Identify
the scalar clock values of the events and the timestamps of the messages
exchanged among the 5 processes shown in Fig. 1. Initially, the scalar clocks
of all the 5 processes are 0. Use R1
and R2 for updating the scalar
clocks. Assume d=1. [5]
Q.1 (b) Consider
the spanning tree shown in Fig. 2. Each node of this tree stores an integer
value. For each node, the node label corresponds to the stored integer value.
The objective is to determine the sum of all the integer values stored in the
tree. Describe the step-by-step procedure by which the root node (i.e., node 5)
notifies all the nodes of the spanning tree to initiate the procedure for
computation of the sum of all integers and how the sum is computed over all the
integers. (Hint: Apply broadcast and convergecast algorithms).
[5]
Fig. 2
Q.1
(c) Consider the following history of message exchange among the 4
processes p1, p2, p3 and P4.
•
p1 sent 8
messages to p2 • p1 sent 2 messages to p3
•
p1 sent 5
messages to p4 • p2 sent 1 message to p1
•
p2 sent 6
messages to p3
•
p2 sent 11
messages to p4
•
p3 sent 7
messages to p1 • p3 sent 3 messages to p2 • p3 sent 9 messages to p4
•
p4 sent 2
messages to p1
•
p4 sent 10
messages to p2
•
p4 sent 5
messages to p3
(i)
Determine the contents of the
SENT array of the 4 processes using Raynal-SchiperToueg algorithm. Assume that
all the 4 processes are aware of the complete history of message transmission. [1]
(ii)
Suppose the following are the
contents of the DELIV arrays of p1, p2, p3 and
p4:
•
for p1, DELIV1
= [0 1
5 2] • for p2, DELIV2 = [7 0
3 7] • for p3, DELIV3 = [2 6
0 1]
•
for p4, DELIV4
= [5 8
8 0]
Now, p1
sends message m14 to p4, p2 sends message m24
to p4, p3 sends message m31 to p1
and p4 sends message m42 to p2. Using
Raynal-Schiper-Toueg algorithm, determine for each of m14, m24,
m31 and m42, whether buffering is required or not for
maintaining causal ordering of messages and why. [4]
Q.2. Consider the spanning tree shown in Fig. 3.
Node N11 holds the privilege.
Using the knowledge of Raymond’s tree-based
algorithm, answer the following questions. (a)
Determine
the values of the HOLDER variables of each of the nodes. [12] (b) Redraw the spanning tree of Fig. 3 by replacing the undirected edges
with directed edges.
[1]
(c)
If now the privilege migrates to N19, the HOLDER
variables of how many nodes need to be reset? Identify all the nodes which need
to reset their HOLDER variables and the new values of the HOLDER variables of
these nodes. [2]
Q.3 For a Chord ring of m = 7, there are 11 nodes –
N2, N19, N26, N31, N54, N76, N89, N101, N109, N112 and N126 and 10 keys – K3,
K8, K26, K29, K60, K80, K97, K107, K110 and K126.
(a)
Show with the help of a
diagram, the arrangement of the nodes along the Chord ring. [1]
(b)
Identify on which node each of
the above mentioned keys will be placed for this Chord ring. You should clearly
mention the reason for placing each key on a particular node.
[(0.5x10=)5+1= 6]
(c)
Suppose for this Chord ring, a
lookup for K107 is initiated at N19. Describe the step-bystep procedure by
which K107 can be located using the simple
lookup algorithm. [4] (d) Determine the finger
tables for N26 and N109 for this Chord ring. [2 + 2 = 4]
*************************
No comments:
Post a Comment