Birla Institute of Technology &
Science, Pilani
Work-Integrated Learning Programmes
Division
Second Semester 2017-2018
Comprehensive Examination
(EC-3 Make-up)
Course No. :
SS ZG526
Course Title :
DISTRIBUTED COMPUTING
Nature of Exam
: Open Book
Weightage
: 45%
Duration : 3 Hours
Date of Exam
: 28/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) 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.
Initially, the vector clock of
each of the 4 processes is [0 0 0 0] and d = 1. [5]
Q.1 (b) Apply
Singhal-Kshemkalyani’s differential technique to determine the progress of
vector clocks at each of the 4 processes shown in Fig. 1 and the contents of
the messages exchanged among them. Initially, the vector clock of each of the 4
processes is [0 0 0 0].
[5]
Q.1 (c) Apply
Fowler-Zwaenepoel’s direct-dependency technique to determine the progress of
vector clocks at each of the 4 processes shown in Fig. 1 and the contents of
the messages exchanged among them. Initially, the vector clock of each of the 4
processes is [0 0 0 0].
[5]
Q.1 (d) Identify
the events for which the vector clock values obtained by applying
SinghalKshemkalyani’s differential technique and Fowler-Zwaenepoel’s
direct-dependency
technique differ?
[1]
Q.2 (a) Find the
heights of all the events occurring at the 3 processes shown in the space-time
diagram of Fig. 2. The timestamps of events a, g and m is 3, 5 and 1 respectively.
Assume d
= 1. [8] a b c d e f
Q.2 (b) Consider the money transfer scenario shown in the timing diagram of
Fig. 3. S1 and S2 are two sites of a distributed system which maintain bank
accounts A and B respectively. C12 is the communication channel from
site S1 to site S2 and C21 is the communication channel from site S2
to site S1. The dashed vertical lines denote the different time instants of
this timing diagram. Initially, at time instant t1, account A has
$1700 and account B has $1000. Between time instants t1 and t2,
S2 initiates a transfer of $90 from account B to account A. Between time instants t2 and t3,
S2 again initiates a transfer of $45 from account B to account A. S1
receives the first money transfer message after t2 and the second
money transfer message after t3. Between time instants t3
and t4, S1 initiates a transfer of $119 from account A to
account B. S2 receives this money transfer message after t5. These 3
money transfer messages are shown by the 3 bold arrows in the diagram.
i)
Determine the states of
channels C12 and C21 at the different time instants for
Fig. 3. [2]
ii)
Assume that the Chandy-Lamport
algorithm is executed on this distributed system for recording the global
snapshot. S1 initiates the snapshot recording algorithm by sending a marker to
S2 after time instant t1. S2 receives this marker after time instant
t4 and sends a marker to S1. S1 receives this marker after t5.
The sending and the receiving of markers are shown using dotted arrows in Fig.
3. Describe how and when the
Chandy-Lamport algorithm records the local states of S1 and S2 and the states
of the channels C12 and C21. Note that the amount of
$2700 in the system should be conserved in the recorded global state. [4]
Q.3 (a) Consider a distributed system consisting of 14 processes as depicted
in Fig. 4.
The following dependencies exist among the
processes:
•
p1 is blocked
and is waiting for p2 to release some resource
•
p2 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 and p11 to release some resources
•
p8 is blocked
and is waiting for p11 to release some resource • p10 is blocked and is waiting for p8 to
release some resource
•
p11 is blocked
and is waiting for p12 to release some resource
•
p12 is blocked
and is waiting for p13 and p14 to release some resources
•
p13 is blocked
and is waiting for p10 to release some resource
•
p14 is blocked
and is waiting for p3 and p4 to release some resources
i) Draw the WFG for the above scenario. [1] ii) Identify all the cycles that exist in the WFG obtained in (i). [3]
Q.3 (b) For a synchronous system consisting of 30
processes, what is the maximum number of Byzantine processes that can be
tolerated so that the Byzantine agreement problem can be solved? [1]
Q.3 (c) Fig. 5
shows the arrangement of nodes and a key along a Chord ring with m = 9. K480 is
to be located using the scalable lookup
algorithm and the search is initiated at N80. List the entries of the
finger tables of the relevant nodes (i.e., the ones which will be used in the
search) and also describe the steps followed by scalable lookup algorithm to locate
K480. [10]
*************************
No comments:
Post a Comment