CSE 291 About time
2018 May 14: Homework 3

Due date

May 21, 5pm.

About time

NTP and Cristian’s algorithm

At 9:23:223 (hr:min:msec) local time, server C requests the time from server N. At 9:23:726 local time, server C receives a reply from N with a timestamp of 9:23:102.

What is the skew of C’s clock with respect to N, assuming there is no processing time at N to reply to the message?

Assuming that C and N’s clocks were equal at some point in the past, is C’s clock going too fast, or too slow, with respect to N?

Types of clocks

On the ieng6 servers (e.g., ieng6-201.ucsd.edu), read the man page for the clock_gettime() system call. This system call allows you to get the time relative to one of several clocks in the system. The CLOCK_REALTIME clock is the “wall clock” time representing the real time (kept in sync with a protocol like NTP), CLOCK_REALTIME_COARSE also represents real-time, however at a coarser granularity. The CLOCK_MONOTONIC clock is guaranteed to never decrease, however its absolute value is meaningless, and the CLOCK_THREAD_CPUTIME_ID clock is very precise, however its absolute value is meaningless and is not necessarily even the same as the per-thread clock on other CPU cores.

Describe an example of a real-world application that could best make use of each type of clock.

Using the clock_getres() system call, indicate how precise each of the above clocks are, in terms of nanoseconds.

Lamport and vector clocks

Imagine that three processes, Client 1, Client 2, and Server, are exchanging messages and initiating local events. The following events occur in this system:

  • Event 1: Client 1 modifies Resume.doc
  • Event 2: Client 1 sends Resume.doc to the server
  • Event 3: The server receives Resume.doc
  • Event 4: Client 2 sends Schedule.xls to the server
  • Event 5: The server receives Schedule.xls
  • Event 6: The server sends Resume.doc to Client 2
  • Event 7: Client 2 receives Resume.doc
  • Event 8: The server sends Schedule.xls to Client 1
  • Event 9: Client 1 receives Schedule.xls
  • Event 10: Client 1 modifies Schedule.xls
  • Event 11: Client 1 sends Schedule.xls to the Server
  • Event 12: The server receives Schedule.xls
  • Event 13: The server sends Schedule.xls to Client 2
  • Event 14: Client 2 receives Schedule.xls
  • Event 15: Client 2 modifies Schedule.xls
  • Event 16: Client 2 sends Schedule.xls to the Server
  • Event 17: The server receives Schedule.xls
  • Event 18: The server sends Schedule.xls to Client 1
  • Event 19: Client 1 receives Schedule.xls

Using this sequence of events, write out the Lamport Clock representation of each timestamp, using the notation L([event]) = [Lamport timestep]. For example, L(e1) = 1

Next, write out the vector time representation of each timestep.

UCSD Piazza study follow-up questions

Within the past 2 weeks:

  • How often did you view Piazza posts?

    • Never
    • Occasionally
    • A few times per week
    • About every day
    • Multiple times per day

  • How did you access Piazza content? (check all that apply)

    • www.piazza.com on laptop/desktop
    • www.piazza.com on mobile device (phone, tablet)
    • Reading posts in automated emails
    • None of the above (or did not use Piazza)

  • On a scale of 1-5 (1 = Not at all helpful, 5 = Very helpful):

    • How helpful was Piazza for course logistics?
    • How helpful was Piazza for completing the assignment?

Submission instructions

Submit a PDF of your solution to GradeScope