Cloud COmputing

Problem 1 (Quickie questions):

1. TCP provides a reliable and in-order byte-stream abstraction but UDP provides neither reliability nor in-order delivery. True or false?
2. A TCP socket is identified by a four-tuple consisting of …. (fill in the blanks with four entities).
3. After a TCP server has been started, what is the first command it must execute in order to initiate a TCP connection? What is the first command on the client side? Mention the programming language you are assuming.
4. How many unknown variables are there to be determined in GPS and what are they?
5. What is an important difference between NTP and the Berkeley time synchronization protocol?
6. In a distributed system using logical timestamps, it is often convenient to ensure that no two events (even those happening on different machines) ever have the same timestamp. Lamport clocks consisting of a scalar integer as we saw in class clearly do not ensure this property. What is a simple adaptation of Lamport clocks to ensure that all events have unique logical timestamps? Note: The answer is not vector clocks, and your answer must preserve the property that if a → b, then ts(a) < ts(b).
7. For two events a and b in a distributed system, it is always the case that either a → b or b → a. True or false?
8. Vector clocks establish a total order across all events unlike Lamport clocks. True or false?

Problem 2 (Clock synchronization):

4. ** Consider Figure 6-6 in the text used to explain the Network Time Protocol (NTP). Derive the expression for the offset of A relative to B in terms of T₁, T₂, T₃, and T₄.
5. In Figure 6-6, suppose the one-way delay from A to B were not equal to that from B to A and their values were not known. Can you still accurately estimate the offset ? Explain why or why not?
6. Suppose two clocks are perfectly synchronized at some absolute time t=0. Suppose their maximum drift rate is 10^-5 /s. How often at least should they use NTP to re-synchronize their clocks in order to bound their offset to at most 5s.
7. Give two reasons why reference broadcast synchronization or receiver-based synchronization (RBS) is more accurate than NTP in wireless network settings.

Problem 3 (Logical clocks):

1. Suppose process P₁ sends a message m at logical (Lamport) time T₀ = 20 that is received by process P₂ at logical time T₁. Give one example of a value that T₁ can take and one example of a value T can not take.
2. Assume that a total of exactly three events have occurred in the above setting: send(m), receive(m), and one other event e with logical timestamp T₂. Give an example of e and T₂ such that e is concurrent with the send(m), i.e., neither e happens before send(m) nor send(m) happens before e.
3. ** In the totally ordered multicasting example using logical clocks (Section 6.2.1 in the text), each process multicasts an acknowledgment for each message to all processes. A process delivers a queued message to the application only when that message is at the head of its queue, i.e., has the lowest (sender’s) logical timestamp, has been acknowledged by each other process. Suppose one of the processes P₁ in the group currently has message m₂ at the head of its queue with logical timestamp ts(m₂) and the message has been acknowledged by all processes, i.e., it is ready to be delivered to the application. Suppose the most recent message delivered by P₁ to its application was m₁ with logical timestamp ts(m₁) < ts(m₂). Assuming FIFO delivery and no loss, give a formal argument for why it is not possible for another message m* with logical timestamp ts(m*) < ts(m₂) to show up in P1’s queue after it has already dequeued and delivered m₂.
4. Suppose we modified the above totally ordered multicast protocol as follows. Each process only sends an acknowledgment to the sender. A process delivers a message if it is at the head of its queue and and at least T=10s have passed. Show with a precise example why this protocol is incorrect, i.e., it can result in different processes delivering messages in different orders to their applications. Your example must
   • not violate FIFO delivery or no-loss assumptions; and
   • Have each event marked precisely with a corresponding logical timestamp and an absolute real timestamp.

Problem 4 (Causal order): We have seen that vector clocks exactly capture the happens-before relationship, i.e., for any two events a and b, VC(a) < VC(b) if and only if a → b.

1. Assume a group of four processes. Give an example of two concurrent events by stating their corresponding vector clocks.
2. Suppose each process maintained both a vector clock and, just for the sake of this question, also maintained a logical (Lamport) clock. Show a simple scenario consisting of send, receive, and other local events as needed consisting of three concurrent events x, y, and z such that ts(x) < ts(y) and ts(x) > ts(z). Your example should also show the vector clocks for those three events. Either use a timing diagram (like Figure 6-13 in the text) or precisely state for each event the real time, logical time, and vector clock time and list all of the events in real-time order.
3. In the causally ordered multicast example (Section 6.2.2), we (1) modified the use of vector clocks to only adjust the vector clock upon send or receive events, and (2) required the following two conditions to be met before permitting delivery of a message m sent by P_i at a receiver P_j to its application (i) ts(m)[i] = VC_j[i]+1; (ii) ts(m)[k] VC_j[k] for all k
   1. Suppose we did not enforce the condition that vector clocks are only adjusted upon send and receive events and instead allowed them to be incremented even for local events. Does the above protocol still achieve causally ordered multicast? Explain why with a proof or why not with a counter-example.
   2. Suppose we changed the second condition for delivering a message by changing the less-than-or-equal-to to equal-to, i.e., ts(m)[k] = VC_j[k]. As this modification is a tightening of the condition, it will of course preserve the causal order of delivered multicast messages. But explain with an example (similar in spirit to Figure 6-13 in the text), what goes “wrong” with this change.