PracticeQ Time Fault Tolerance Snapshot

a. P1 -> R4
True, P1 -> Q2, Q2 -> Q4, Q4 -> R3, R3 -> R4, so P1 -> R4
b. Q1 -> R4
True, Q1 -> R4
c. P1 -> Q1
False, Concurrent
d. R1 -> Q6
False, cannot say that

2. Suppose two servers, S1 (San Francisco) and S2 (New York), each use NTP to synchronize their clocks with a reference UTC clock. If NTP provides an accuracy of 50ms, are the statements below True or False? Briefly explain your answer. (4 points):

a. With NTP accuracy of 50ms, the clocks on S1 and S2 may be off by up to 50
milliseconds from one another.
False, they may be off by 2*50 = 100 ms

b. If event A at S1 is timestamped at 12:00:00.000 (with its local clock) and event B
at S2 is timestamped at 12:00:00.060 (with its local clock), we can be sure that A
took place before B.
False
Assume true time: 12:00:00.030
Event A is 30 ms earlier than real time
Event B is 30ms later than real time

3. A distributed system logs events with vector clocks:

• Event E1 on Machine X: vector clock [4, 2]

• Event E2 on Machine Y: vector clock [3, 3]
  Determine if there is a causal relationship between E1 and E2 (4 points).

• vp[i] ≤ vq[i] for all i

• there exist some k such that vp[k] < vq[k]

Not true. So no.

4. A popular flight booking website is advertised as having 99.9% availability. Over a month (30 days), the site is used constantly by thousands of users. How many minutes per month can the site be unreachable while still meeting its claimed 99.9% availability (4 points)?

30 days have 24*30 hours, which is 720 hours, which has 720*60 = 43200 minutes, 43200 * 0.001 = 43.2 minutes

5. A hotel booking system uses RPC to reserve rooms. Clients send a "reserve room" request to the booking server. Once the server receives the request, it immediately sends an acknowledgement and then performs the booking.

Alice sent a reservation request but did not receive an acknowledgment. After a timeout,
and unsure if the reservation was successful, she sends another request. Which of the
following statements are true? Briefly explain your answers (3 points).

a. Alice has definitely booked the hotel twice.

Not true, if the first message was lost.

b. After re-sending the request, Alice can be sure that the booking is confirmed.

Not true. Even if ACKed, which is not, Alice cannot be sure.

c. The server probably crashed.

Maybe. Or message was lost.

6. Consider the following three processes which execute activities and exchange messages. Their timelines are shown horizontally, so that time flows from left to right and they are all connected with pairwise FIFO channels. Suppose that P initiates a snapshot right after event B has happened (the marker is shown with a red diamond) (4 points).

Alice runs the Chandy-Lamport protocol and ends up with the cut shown below in purple.
Bob, however, insists that she got it wrong and claims that this cut does not correspond
to a possible consistent cut taken by the Chandy-Lamport algorithm.

a. Who is right? (1p)
Bob is right
b. Why? (3p)
So the marker was sent at the red diamond. If the marker was received by Process Q, then the message P sent at A should already arrived, since it's FIFO, so E should have been in the cut.