DC-FIRST-MID-SEM-REGULAR-17-18

Birla Institute of Technology & Science, Pilani

Work-Integrated Learning Programmes Division

First Semester 2017-2018

Mid-Semester Test

(EC-2 Regular)

Course No.                  : SS ZG526 

Course Title                 : DISTRIBUTING COMPUTING 

Nature of Exam           : Closed Book

Weightage                    : 30%

Duration                      : 2 Hours 

Date of Exam              : 23/09/2017    (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)          Discuss the 4 different features of distributed systems.                                                   [4]

Q.1 (b)          Describe the causal ordering model of communication.                                                    [1]

Q.1 (c)           Define cut of a distributed computation.                                                                          [1]

Q.2 (a)          Consider the space-time diagram shown in Fig. 1 depicting 3 processes.

        Are the following pairs of events causally related? Justify your answer.                      [1 x 4 = 4]

(i)e₁¹ and e₅³ (ii)e₁³ and e₅² (iii)e₃¹ and e₆³ (iv)e₂² and e₆¹

Q.2 (b)          For the space-time diagram of Fig. 1, is the global state {LS₂¹, LS₂², LSe₄³} consists? Give reasons in support of your answer.                                                                             [1]

SS ZG526 (EC-2 Regular)                              First Semester 2017-2018                               Page 2

Q.3 (a)          Identify the scalar clock values of the events and the timestamps of the messages exchanged among the 3 processes shown in Fig. 1. Initially, the scalar clocks of all the 3 processes are 0. Use R1 and R2 for updating the scalar clocks. Assume d = 1.               [4]       

Q.3 (b)          What are the heights of events e₅³ and e₆¹ in Fig. 1?                                       [½ + ½ = 1]

Q.3 (c)          Is the expression (e_x || e_y) Ù (e_y || e_z) Þ e_x || e_z correct for any 3 events e_x, e_y and e_z? Explain your answer.                                                                                                       [1]

Q.4 (a)           Write a short note on Butterfly network by clearly describing the interconnection function and the routing function. Note that your answer should be accompanied with a diagram illustrating the interconnection pattern for an 8-input and 8-output Butterfly network.                                                                                                          [2 + 2 = 4]                                                                                                                   

Q.4 (b)           What are the 2 conditions that must be satisfied by a global state so that we can say that it is a consistent global state?                                                                                               [2]

Q.5 (a)          Determine a BFS spanning tree by applying the synchronous single-initiator spanning tree algorithm using flooding on the graph shown in Fig. 2. Assume node A to be the root node. Clearly show the round numbers in which the QUERY messages are sent by the different nodes.                                                                                                                  [5]              

Q.5 (b)           Describe the different steps of the Birman-Schiper-Stephenson Protocol.                      [2]

**********