Birla Institute of Technology & Science, Pilani
Work-Integrated Learning Programmes Division
First 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 : 04/11/2017 (AN)
Note:
Please follow all the Instructions to Candidates given on the
cover page of the answer book.
All parts of a question should be answered consecutively. Each answer
should start from a fresh page.
Assumptions made if any, should be stated clearly at the beginning of
your answer.
Q.1 (a)
Compute
the scalar clock values of the events and the scalar timestamps of the messages
exchanged among the 4 processes shown in the space-time diagram of Fig. 1.
Assume that initially, the scalar clock values of all the processes is 0 and d = 1. [4]
Q.1 (b)
Compute the vector
timestamps of the events occurring at the 4 processes and the vector timestamps
of the messages exchanged among them as shown in the space-time diagram of Fig.
1. Use R1 and R2 for updating the vector clocks. Assume that initially, the
vector clocks of each of the 4 processes is [0 0 0 0] and d = 1. [5]
Q.2 (a)
Consider the space-time diagram of Fig.
2. Using Birman-Schiper-Stephenson (BSS) protocol, determine the progress of
the vector clocks at each of the 3 processes corresponding to the occurrence of
the different events, timestamps of the messages exchanged among the processes,
conditions that need to be checked before message delivery and buffering of messages
(if required). Note that message a is broadcast by p2 in
event and messages b
and c
are broadcast by p3 in events 
and 
respectively. Assume
that initially the vector clocks of all the 3 processes are [0 0 0]. [6]
and respectively. Assume
that initially the vector clocks of all the 3 processes are [0 0 0]. [6]
SS ZG526 (EC-3 Regular) First Semester
2017-2018 Page 2
Q.3 (a)
Consider
a 3-stage Omega network consisting of 8
processors, 8 memory units and 12 switching elements each of size 2 x 2.
Between each pair of adjacent stages of the network, a link exists between
output i of a stage and input j to the next stage according to the following
interconnection function:
j = (2n – i) % n
Note that for this network, n = 8
and 0 £
i £
7. Draw a diagram depicting the interconnections between the adjacent stages of
this Omega network according to the above mentioned specifications. [5]
SS ZG526 (EC-3 Regular) First Semester
2017-2018 Page 3
Q.3 (b)
Consider a distributed system consisting
of 12 processes as depicted in Fig. 4.
The following
dependencies exist among the processes:
·
p1
is blocked and is waiting for p3 to release some resource
·
p2
is blocked and is waiting for p3 to release some resource
·
p3
is blocked and is waiting for p4 to release some resource
·
p4
is blocked and is waiting for p5 to release some resource
·
p5
is blocked and is waiting for p7 to release some resource
·
p7
is blocked and is waiting for p8 to release some resource
·
p8
is blocked and is waiting for p6, p9 and p12 to
release some resources
·
p12
is blocked and is waiting for p10 to release some resource
·
p10
is blocked and is waiting for p11 to release some resource
·
p11
is blocked and is waiting for p2 to release some resource
i.
Draw
the WFG for the above scenario.
ii.
Assuming that
the WFG determined in (i) is an AND model WFG, determine whether a deadlock
exists in the system with proper reason. If a deadlock exists, identify the
deadlocked processes. [2 + 2 = 4]
Q.4 (a)
A distributed system consists of 12
sites - S1, S2, S3, S4, S5,
S6, S7, S8, S9, S10, S11
and S12. The
request sets for S4, S5 and S6 are R4,
R5 and R6 respectively.
R4 = {S1, S2,
S4, S7, S10}, R5 = {S3,
S5, S7, S8, S9}, R6 = {S6,
S8, S10, S11, S12}
Give an example scenario which
results in a deadlock when sites S4, S5 and S6
simultaneously invoke mutual exclusion using Maekawa’s algorithm. Clearly
mention the sites locked by each of S4, S5 and S6
and the sites for which each of S4, S5 and S6
waits. [3]
SS ZG526 (EC-3 Regular) First Semester
2017-2018 Page 4
Q.4 (b)
Fig. 5 shows the
arrangement of nodes along a Chord ring with m = 9. Determine the finger tables
for N32, N183 and N240. [2 + 2 + 2 = 6]
Q. 5
Consider the spanning tree
shown in Fig. 6. Node O 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. [8]
b) Redraw
the spanning tree of Fig. 6 by replacing the undirected edges by directed
edges. [1]
No comments:
Post a Comment