CS5414 (Fall 2012) Homework 1
Logical Clocks Implementation

Due: 11pm, Sept 4
Relative weight: 5 units

General Instructions. You are expected to work alone on this assignment.

Submit your solution using CMS. No late assignments will be accepted.

To facilitate grading, format your solutions as follows.

• Put your name and net id on each page of your solution.
• Typeset your solution, using 10 point or larger font and use 8.5 x 11 inch paper.
• Use at most one page (both sides, if necessary) for each problem.
• Start each problem's solution on a separate side.

Consider a distributed system, where each processor p has a single core and has a hardware clock Cp. We write Cp(t) to denote the time that Cp displays at the instant the omniscient observer knows the real time to be exactly t. For simplicity, assume that the resolution of Cp is very high and, therefore, "ticks" of this clock are short relative to the length of time required to execute an instruction.

Were Cp perfect, then Cp(t) = t would hold for all values t. But actual hardware clocks do not advance at exactly the same rate as real-time or, for that matter, at the same rates as each other. For the purposes of this problem, assume hardware clocks are kept synchronized within D of each other. Thus, for all processors p and q and all real times t:

0 <= | Cp(t) - Cq(t) | <= D

where | x | denotes the absolute value of x.

Further, suppose the message-delivery delay for the network that connects processors is bounded from below and from above. Specifically, the delay (as measured by the hardware clock at any of the processors) to deliver a message is always a value between DDmin and be DDmax.

1. Recall that a logical clock assigns timestamps to events in a way that is consistent with potential causality. One approach for computing the logical time TS(Ep) for an event Ep is to use the hardware clock on the processor p (say) where Ep occurs. Describe such a scheme that also satisfies the following implementation constraints:
   • There is no piggy-backing of additional information (e.g., timestamps) on any message.
   • No additional messages are exchanged between processors.
   Your scheme is allowed to impose reasonable restrictions on D, DDmax, and DDmin if necessary.

2. Prove the scheme you proposed in 1 satisfies the two requirements of a logical clock:
   1. Distinct events are assigned distinct logical timestamps.
   2. If an event E is potentially cause for another event F then TS(E) < TS(F).