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.

Submission

Please submit your assignment prior to the due date & time via canvas.

Note: submissions must be plain text or PDF files or text entry within Canvas. 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.

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.

Lecture notes: Assigning Lamport & Vector Timestamps :

Questions

Question 1.  

You have the following timestamps:

Time is expressed in seconds as a floating-point number. Using NTP, what is the new time? Compute this by adding the offset, theta, to the client receives response time.

Note: NTP refers to pairs of systems that synchronize clocks as peers. This is because in the symmetric mode of the protocol, which is designed for time servers to synchronize with each other, both systems maintain information about each other and act as peers. In SNTP, there is a clear client-server relationship. In this case of NTP operating in procedure call mode (the same as SNTP), where a client gets time from a server, A refers to the client and B refers to the server in the NTP RFC.

Also note: Don’t use a calculator that limits its precision to ten or so decimal places. If you use Linux’s bc, don’t forget to first run the command scale=6 within bc to enable computation with six digits of decimals.

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 P₀ starts at 0 and event a gets assigned a Lamport timestamp of 1.

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 (P₀ , P₁ , P₂ ).

Question 6.  

Which events are concurrent with event b?