Scalable Dist Systems Homework #3

CS 6650 Scalable Dist Systems
Homework #3      [100 points]

INSTRUCTIONS: Please provide clear explanations in your own sentences, directly answering the question, demonstrating your understanding of the question and its solution, in depth, with sufficient detail.   Submit your solutions [PDF preferred].  Include your full name.  Do not email the solutions.

Study Chapter 14 and 15 from Coulouris Book    Clocks and Time, Global States, Consensus

Answer the following questions using explanation and diagrams as needed.  No implementation needed.
1.    14.4              [5 points]

2.    14.7              [10 points]

3.    A system of four processes, (P1, P2, P3, P4), performs the following events:     [25 points]
a.           P1 sends a message to P3 (to event e). 
b.    P1 receives a message from P3 (from event g). 
c.           P2 executes a local event. 
d.    P2 receives a message from P3 (from event f). 
e.          P3 receives a message from P1 (from event a). 
f.          P3 sends a message to P2 (to event d). 
g.          P3 sends a message to P1 (to event b). 
h.    P4 executes a local event. 
When taking place on the same processor, the events occur in the order listed. 
Assign Lamport timestamps to each event. Assume that the clock on each processor is initialized to 0 and incremented before each event. For example, event a will be assigned a timestamp of 1. 
 
a.    Assign vector timestamps to each event in question 2. Assume that the vector clock on each processor is initialized to (0,0,0,0) with the elements corresponding to (P1, P2, P3, P4). For example, event a will be assigned a timestamp of (1, 0, 0, 0). 
b.    Which events are concurrent with event d? 

4.    You are synchronizing your clock from a time server using Cristian's algorithm and observe the following times:                             [15 points]
•    timestamp at client when the message leaves the client: 6:22:15.100 
•    timestamp generated by the server: 6:21:10.700 
•    timestamp at client when the message is received at client: 6:22:15.250 
    To what value do you set the client's clock? 
    If the best-case round-trip message transit time is 124 msec (0.124 sec), what is the error of the clock on the client? 

5.    14.14                                      [15 points]

6.    15.9                                    [10 points]

7.    Using Chandy-Lamport algorithm, show when each process records its local state (you can annotate the figure) and list the channel states for each process captured in the snapshot. Black dotted lines are marker messages. Red lines are messages (A to F)                [20 points]