CS5414 (Fall 2010) Homework 2
More on Causality and Clock Implementation
Due: 9:00am, 9/17/2010
Relative weight: 8 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.
Solutions that do not satisfy the formatting guidelines will be
returned, ungraded.
Problem 1
The distributed system in homework 1 was synchronous.
In this problem, we consider a distributed system that is completely asynchronous.
Assume that:
-
Each processor p has a unique identifier, IDp.
-
Each processor executes instructions at its own non-zero (though not necessarily
fixed) rate.
-
Each processor p has a single core and has a hardware clock Cp.
The hardware clock increases monotonically with the passage of real-time,
but the hardware clocks at different processors
are not synchronized with each other and their respective rates
of advance differ.
Hardware clocks may be read but not changed by any program.
-
Message delivery time between processors is finite but unbounded.
Thus, no assumptions can be made about parameters D, DDmin, and DDmax in homework 1.
Obviously, giving real-time execution bounds for programs
that run in such a system is pointless, so nobody expects them.
(1.1) Describe an implementation of logical clocks for this distributed system.
Your implementation must satisfy the two
two requirements of a logical clock:
-
Distinct events are assigned distinct logical timestamps.
-
If an event E is potentially cause for another event F then
TS(E) < TS(F).
Your implementation must satisfy the following:
-
It may read the real-time clock but it may not employ any other long-term storage,
such as the counters used in the logical clock implementation from Lamport.
-
Additional information may be included in messages that are sent between processors.
-
No additional message exchanges are permitted beyond those required by the programs
already been executed.
(1.2) Argue that your implementation satisfies the two requirements of a logical clock:
-
Distinct events are assigned distinct logical timestamps.
-
If an event E is potentially cause for another event F then
TS(E) < TS(F).
Problem 2
Recall that a vector clock VC maps each event E to a timestamp VC(E)
and satisfies the following strong clock condition:
E --> F if and only if VC(E) < VC(F)
Vector clocks are not the only method for implementing a mechanism that satisfies the
strong clock condition, though.
A prime clock PC is constructed as follows.
Assume that every processor i is assigned and knows a unique prime number pi.
Assume also that each processor has a way to store integers that can grow
arbitrarily large.
-
Each processor i maintains a counter PCi, which is initially set to pi.
-
Whenever a local event E occurs at processor i, the following is executed:
PCi := PCi * pi
The timestamp PC(E) of E is the value of PCi after the update.
-
Whenever a send event E for a message m occurs at processor i,
the following is executed:
PCi := PCi * pi;
timestamp TS(m) = PCi is included as part of m
The timestamp PC(E) of E is the value of PCi after the update.
-
Whenever a receive event for a message m occurs at processor i,
the following is executed
PCi := PCi * TS(m) * pi
The timestamp PC(E) of E is the value of PCi after the update.
(2.1)
Give an implementation for a relation "<" on values from prime clocks
that causes values obtained from prime clocks to satisfy the strong clock condition.
That is, give a procedure for computing whether PC(E) < PC(F) holds, such that
E --> F if and only if PC(E) < PC(F)
is valid.
(2.2)
Prove that prime clocks satisfy the weak clock condition:
E --> F implies PC(E) < PC(F).
(2.3)
EXTRA CREDIT
Prove that prime clocks satisfy the strong clock condition:
E --> F if and only if PC(E) < PC(F)
Hint for all parts:
The Fundamental Theorem of Arithmetic asserts that every
positive integer greater than 1
has a unique factorization as a product of prime numbers.