Assignment 3

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

Introduction

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

  2. 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.

    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?
  4. 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: 10:44:20.400
    • timestamp generated by the server: 9:20:10.200
    • timestamp at client when the message is received at client: 10:44:21.200
    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?
  5. Look at the intel 8254x family of Gigabit Ethernet controllers ( datasheet). Explain the multicast support available in these chips (e.g., filtering by hashing an address? ... exact addresses?).
  6. While IP multicast failed to gain widespread use for many "generic" IP-based applications, it is a key component of IPTV (TV broadcast over IP) deployments. Read:
    1. According to the second article, how much network bandwidth is needed for 100 channels?
    2. What is an advantage of using multicast for IPTV?