Assignment 3

Due Wednesday, October 5, 2016 6:55pm via sakai

Introduction

Please answer the questions precisely and concisely. Every question can be answered in one or at most a few sentences.

Submit your work via sakai as a plain text or pdf document. Be sure to submit only a plain text or pdf file. Microsoft Word, Apple Pages, Adobe Illustrator, or any other formats that require me to open an application will not be accepted and will result in a grade of 0 for the assignment. You may submit an HTML-formatted assignment if your answer your questions directly in sakai's editor rather than submitting an attachment.

Reading

Time, Clocks, and the Ordering of Events in a Distributed System, Leslie Lamport.
For question 1. 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.
RFC 5905.
For question 3. The NTP (SNTP) formula is in section 8 (On-wire Protocol). 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.
Why Vector Clocks are Easy, Basho Block, 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.
Clock synchronization: lecture notes
Assigning Lamport & Vector Timestamps
For questions 4-6.

Questions

  1. How does Lamport define concurrent events?
  2. From the Why Vector Clocks are Easy paper, how can you tell if one vector clock is a descendent of another vector clock?
  3. You have the following timestamps:
    Client request sent: 7:12:10.100
    Client receives response: 7:12.10.150
    Server receives request: 7:11:59.900
    Server sends response: 7:11:59.920

    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)?

  4. events

    Events on three processes

  5. The table above shows ten events (a, b, ..., j) taking place among 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.
  6. a. 1 b. c. d. e.
    f. g. h. i. j.
  7. 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).
  8. a. (1, 0, 0) b. c. d. e.
    f. g. h. i. j.
  9. Based on the vector timestamps, which events are causally dependent on event c (that is, which events follow c and are causally related)?