Lamport’s paper: Time, Clocks, and the ordering of Events in a Distributed System

Anomalous behavior occurs because Lamport’s logical clocks are not enough to guarantee that the total ordering of events derived from the unique partial ordering and a non-unique total ordering is not enough to guarantee that the ordering is correct with respect to physical time.

He gives two conditions PC1 and PC2:

PC1: There exists a constant $ kappa $ << 1 such that for all i:

$ |frac{dC_{i}}{dt} – 1| < kappa $

PC2: For all i, j:

$ |C_{i}(t) – C_{j}(t)| < epsilon $

PC1 says that individual clock drift in the system must be less than some constant $ kappa $. PC2 says that clocks must be synchronized so that the difference in time between any 2 clocks does not exceed $ epsilon $.

**This is what I do not understand.** He says that anomalous behavior is impossible if this proposition holds, deduced from PC2.

proposition:

PC2 implies $|C_{i}(t + mu) – C_{j}(t)| > 0$ if $frac{epsilon}{1 – kappa} leq mu$.

I have no idea where he comes up with this, maybe my math isn’t too great.

Note: $mu$ is a constant that must be less than the shortest transmission time for interprocess messages.

PC1 implies $|C_{i}(t + mu) – C_{i}(t)| > (1 – kappa)mu$. This is apparent because (1 – $kappa$) is less than 1. But apparently he combines this with PC2 to deduce the proposition.

How does he arrive at this??