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?

      An event a is concurrent with an event b if a neither a happened before b nor b happened before a (neither a → b nor b → a).
   2. What is Lamport's definition of concurrent events using the concept of causality?
      Two events are concurrent if neither can causally affect the other event.

2. A system of four processes, (P₁, P₂, P₃, P₄), performs the following events:

   1. P₁ sends a message to P₃ (to event e).
   2. P₁ receives a message from P₃ (from event g).
   3. P₂ executes a local event.
   4. P₂ receives a message from P₃ (from event f).
   5. P₃ receives a message from P₁ (from event a).
   6. P₃ sends a message to P₂ (to event d).
   7. P₃ sends a message to P₁ (to event b).
   8. P₄ 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. 5
   c. 1
   d. 4
   e. 2
   f. 3
   g. 4
   h. 1
   
3. 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 (P₁, P₂, P₃, P₄). For example, event a will be assigned a timestamp of (1, 0, 0, 0).
      a. (1, 0, 0, 0)
      b. (2, 0, 3, 0)
      c. (0, 1, 0, 0)
      d. (1, 2, 2, 0)
      e. (1, 0, 1, 0)
      f. (1, 0, 2, 0)
      g. (1, 0, 3, 0)
      h. (0, 0, 0, 1)
      
   2. Which events are concurrent with event d?
      b, g, h.
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?

      The elapased time is 21.00 - 20.400 = 0.800. The time is set to the server's time + ½(elapsed time) = 9:20:10.200 + ½(0.800) = 9:20:10.600.

   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?

      The error is ±½(the region of uncertainty). This region is (the elapsed time) - (the best-case round-trip time) = 0.800 - 0.124 = 0.676 sec. The error is half of that, or ± 338 msec.

      Note that you have to be careful if you want to plug numbers into the formula. 124 msec is not T_min. It's the round-trip latency, or 2T_min.

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?).
   These controllers allow:
   1. 16 exact matches of an address.
   2. A 12-bit hash lookup onto a 4096-bit table.
   3. Promiscuous multicast to accept all multicast ethernet packets.