Introduction

Please answer the questions precisely and concisely. Every question can be answered in one or at most a few sentences. I will not have the patience to read long paragraphs or essays and you may lose credit for possibly correct answers.

Note: submissions must be be plain text or pdf files or HTML within sakai. Other formats, such as Microsoft Word, Apple Pages, or Adobe InDesign will not be accepted.

Reading

RFC 5905
The NTP (SNTP) formula is in section 8 (On-wire Protocol) on pages 27 and 28. That’s all you need to read but you may want to look through the rest of the RFC to understand the complexities of computing clock errors and why I didn’t go into depth on this topic in class. All you need to compute is the the clock offset relative to the server. Note that they refer to the offset as theta (θ).
Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System
For question 2. read pages 558–561 (the document starts at page 558). This is the classic paper that introduces, among other things, Lamport clocks and partial ordering. Unfortunately, the relativity references do not add clarity to this paper.
Lecture notes: Assigning Lamport & Vector Timestamps
Bryan Fink, Why Vector Clocks are Easy, Basho Blog, January 29, 2010
This is a short overview of vector clocks with simple examples in the context of multiple processes updating a single value in a database. You only need to read up to How to do this in Riak. The rest of the document discusses how to use vector locks in the Riak distributed database.

Questions

Question 1

You have the following timestamps:

Operation timestamp
Client sends request: 8:22:10.300
Client receives response: 8:22:10.350
Server receives request: 8:10:00.600
Server sends response: 8:10:00.610

Time is expressed as hours:minutes:seconds.decimal_seconds.

In the case of a client synchronizing with the server, A refers to the client and B refers to the server in the NTP RFC. Using NTP, what is the new time (add the offset, theta, to the client receives response time)?

Question 2

How does Lamport define concurrent events? (Just the high-level definition, not using timestamps.)

Question 3

From the Why Vector Clocks are Easy paper, how can you tell if one vector clock is a descendent of another vector clock?

Question 4

The diagram below shows nine events (a, b, … i) on three processes.



Assign Lamport timestamps to each event. The event clock on each process is initialized to zero at the beginning and incremented prior to timestamping each event. For instance, the clock on P0 starts at 0 and event a gets assigned a Lamport timestamp of 1.
a. 1 b. c. d. e.
f. g. h. i.  

Question 5

Using the same set of events as in the previous question, assign vector timestamps to each event. The event clock vector at each process is initialized to all zeros at the beginning and a process increments its position in the vector prior to timestamping each event. Process positions in the vector are (P0, P1, P2).

a. (1, 0, 0) b. c. d. e.
f. g. h. i. j.

Question 6

Which events are concurrent with event b?