1. Consider a cut of a distributed computation, C = {c1, c2, c3, c4}. VTc1 = {5, 2, 4, 7}; VTc2 = {3, 6, 4, 6}; VTc3 = {4, 5, 7, 4}; VTc4 = {3, 4, 6, 8}. What is the value of VTc? Is C a
consistent cut?
VTc = {5,6,7,8}
VTc is a consistent cut because VTc = {VTc1 [1], VTc2 [2], VTc3 [3], VTc4 [4]}
2. Identify the consistent (if any) and strongly consistent (if any) global states in the following diagram.
Consistent global state: {LS12, LS23, LS33}
Strongly Consistent global state: {LS11, LS21, LS31}
3. What are the consistent global states in the following space-time diagram?
The consistent global states are:
{LS11, LS21, LS31}, {LS12, LS21, LS31}, {LS12, LS22, LS31}, {LS12, LS23, LS31}, {LS13, LS21, LS31}, {LS13, LS22, LS32}, {LS13, LS22, LS33}, {LS13, LS23, LS31}, {LS13, LS23, LS32}, {LS13, LS23, LS33}, {LS13, LS23, LS34}, {LS14, LS21, LS31}, {LS14, LS22, LS31}, {LS14, LS22, LS32}, {LS14, LS22, LS33}, {LS14, LS23, LS31}, {LS14, LS23, LS32}, {LS14, LS23, LS33}, {LS14, LS23, LS34}
4. Consider the following two space-time diagrams. Use SES (Schiper-Eggli-Sandoz Algorithm) to decide whether a message is to be buffered or delivered, and indicate it as such in the space-time diagram. (For instance, you may use dotted arrows to indicate buffering and solid arrows to indicate delivery). Explain the contents of V_Pi (i = 1, 2, 3) for all processes after every message is sent or received. Also, specify the vector clock of each process for every event (sending/receiving a message).
(i)
<1,0,0> <2,0,2> <3,0,2> <4,4,2>
M2 M5
M6
<0,1,1> <1,2,1<1,3,1> <1,4,1>
M1 M4
M3
<0,0,1> <0,0,2> <1,3,3> <3,3,4>
V_Pi’s (i = 1,2,3) after Mi sent or received
M1 / M2 / M3 / M4 / M5 / M6V_P1 / Empty / (P2,<1,0,0>) / (P2,<1,0,1>) / ß / +(P3,<3,0,2>) / ß
V_P2 / Empty / Empty / Empty / (P3,<1,3,1>) / ß / +(P1,<1,4,1>)
V_P3 / (P2,<0,0,1>) / ß / +(P1,<0,0,2>) / ß / ß / ß
Note that the values of V_Pi’s are the ones that are updated after corresponding Mi’s are sent or received. For example, after M2 is sent, V_P1 is as shown: (P2,<1,0,0>).
(ii)
<1,0,0> <2,0,0> <3,3,3> <4,4,3>
M5
M2
M6
<0,1,1> <1,2,1> <1,3,1> <1,4,1>
M1 M3
M4
<0,0,1> <1,3,2> <1,3,3> <2,3,4>
V_Pi’s (i = 1,2,3) after Mi sent or received
M1 / M2 / M3 / M4 / M5 / M6V_P1
/ Empty / (P2,<1,0,0>) / ß / (P2,<1,0,1>) / +(P3,<2,0,0>) / (P2,..)+(P3,<2,3,1>)V_P2 / Empty / Empty / (P3,<1,3,1>) / ß / ß / +(P1,<1,4,1>)
V_P3 / (P2,<0,0,1>) / ß / ß / +(P1,<1,3,3>) / +(P2,<1,0,1>) / ß
5. Consider the following space-time diagram. Using BSS algorithm, what should be the vector clocks of P1, P2, and P3 at the end? (i.e., after all the message exchanges). Order the messages (using the BSS algorithm) before marking the clock values).
(i)
At the end,
VTP1 = (1,1,1)
VTP2 = (1,1,1)
VTP3 = (1,1,1)
(ii)
At the end,
VTP1 = (1,1,1)
VTP2 = (1,1,1)
VTP3 = (1,1,1)
6. Consider the following space-time diagram. Label the event points using:
i. Lamport’s logical clocks
ii. Vector clocks
iii. Time of cuts Ca (={C1,C2}) and Cb (={C3,C4}).
(i) Lamport’s logical clocks
(1) (2) (3) (4) (5) (6)
(1) (2) (3) 4) (5) (6)
(ii) Vector clocks
(1,0) (2,0) (3,0) (4,2) (5,2) (6,5)
(0,1) (0,2) (2,3) (3,4) (3,5) (3,6)
(iii) Time of cuts
Ca = (C1, C2) = (2,3)
Cb = (C3, C4) = (5,5)
7. A distributed computation application uses Huang’s termination detection algorithm.
Computation starts at process P (which acts as the controlling agent). P asks P1 to do some computation. P1 requests P2 to do part of its computation. P2 passes on part of its job to P3. After some time, P1 uses P4 to carry out another part of its computation. Draw a process-tree diagram and mention the weights assigned to each process.
Now, the computation completes in the following sequence: (a) P4 completes and hands over the results to P1; (b) after that, P3 hands over the results to P2; (c) then, P2 passes the results to P1; (d) finally, P1 hands over to P. Draw the process-tree diagram for each of the step (a)-(d) and indicate the weights at each process.
W = 1(initially)
W = 0.5
W = 0.5
W = 0.125
W = 0.25 W = 0.125
W = 0.125
W = 0.125
(a) P4 sends to P1
W = 0.125 + 0.125 = 0.25
W = 0.125 (before sending)
W = 0 (after sending)
(b) P3 sends to P2
W = 0.125 + 0.125 = 0.25
W = 0.125 (before sending)
W = 0 (after sending)
(c) P2 passes the results to P1:
W = 0.25 + 0.25 = 0.5
W = 0.25 (before sending)
W = 0 (after sending)
(d) P1 hands over to P
W = 0.5 + 0.5 = 1
W = 0.5 (before sending)
W = 0 (after sending)
Note:
If you hand over the results and weights directly to P (the controller), it is fine too. You will get full credit for that too.
8. Consider a distributed system that has computers C1 and C2. In C1, integer data type is represented with 32 bits and character with 16 bits. In C2, an integer uses 16 bits while a character uses 8 bits. Now, an Ada program has a procedure RemoteOperate(m: integer; n: character; var x: integer) that can be invoked by C2 on C1. (Such a remote invocation implies that parameters m and n should be passed by C2 to C1 and parameter x should be returned from C1 to C2). Design a packing and an unpacking stub procedure on C2 and C1 to enable the invocation of the procedure RemoteOperate.
Solution:
In the following design, the UNICODE format is considered to be the standard format. The packing procedure converts from the local format to the UNICODE format and the unpacking procedure converts from the UNICODE back to the local machines format.