Assignment 3

Due Wednesday, March 11, 2009 8:25pm in class
(at the start of recitation)

Introduction

Read the lecture notes for Clock Synchronization.

Please answer the questions precisely and concisely. You may need to do a bit of web surfing for many of these questions. 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.

Write neatly. If I have to struggle to figure out what you wrote, you will lose credit. Type your answers if your penmanship is poor.

In the "I shouldn't have to tell you this" department... Should you feel the need to use multiple pages, please fasten the sheets securely. Use a stapler or other permanent fastener. Avoid paper clips since sheets can slide out.

Questions

  1. In AFS, how does a client find out the actual machine on which a specific volume is located? See Managing Volumes in the AFS Administration Guide: http://www.openafs.org/pages/doc/AdminGuide/auagd002.htm
  2. What is validation in Coda?

    See section 1 in the Coda HOWTO: http://www.coda.cs.cmu.edu/doc/html/coda-howto-1.html

  3. What is an advantage of session semantics over UNIX (sequential) semantics?
    Take a look at Coda and Databases: http://www.coda.cs.cmu.edu/misc/databases.html
  4. Compare the types of caching one can perform under CIFS with an exclusive oplock versus a level II oplock.

    Take a look at the Microsoft Developer Network CIFS Protocol Operation article. It has a concise summary of oplocaks.

  5. Read Lamport's paper on Time, Clocks, and the Ordering of Events in a Distributed System.
    1. What is Lamport's definition of concurrent events using the happened before relation?
    2. What is Lamport's definition of concurrent events using the concept of causality?
  6. What is the advantage of a vector clock over Lamport's logical clock?

    (The lecture notes on clock synchronization have been updated.)

  7. A system of four processes, (P1, P2, P3, P4), performs the following events:

    1. P1 sends a message to P3 (to event e).
    2. P1 receives a message from P3 (from event g).
    3. P2 executes a local event.
    4. P2 receives a message from P3 (from event f).
    5. P3 receives a message from P1 (from event a).
    6. P3 sends a message to P2 (to event d).
    7. P3 sends a message to P1 (to event b).
    8. P4 executes a local event.

    When taking place on the same processor, the events occur in the order listed.

    Assign Lamport timestamps to each event. Assume that the clock on each processor is initialized to 0 and incremented before each event. For example, event a will be assigned a timestamp of 1.

    a. 1 b. c. d.
    e. f. g. h.
    1. Assign vector timestamps to each event in question 2. Assume that the vector clock on each processor is initialized to (0,0,0,0) with the elements corresponding to (P1, P2, P3, P4). For example, event a will be assigned a timestamp of (1, 0, 0, 0).
    2. Which events are concurrent with event d?
  8. You are synchronizing your clock from a time server using Cristian's algorithm and observe the following times:
    • timestamp at client when the message leaves the client: 6:22:15.100
    • timestamp generated by the server: 6:21:10.700
    • timestamp at client when the message is received at client: 6:22:15.250
    1. To what value do you set the client's clock?
    2. If the best-case round-trip message transit time is 124 msec (0.124 sec), what is the error of the clock on the client?
  9. You are synchronizing your clock from a time server using SNTP (the Simple Network Time Protocol) and observe the following times:
    • timestamp at client when the message leaves the client: 6:22:15.100
    • timestamp at which the server receives the message: 7:05:10.700
    • timestamp at which the server sends the reply: 7:05:10.710
    • timestamp at client when the message is received at client: 6:22:15.250
    To what value do you set the client's clock?