# algorithm analysis – How does Lamport imply anomalous behavior is impossible given these constraints?

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

Posted on Categories Articles