0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

The constraint as written by Lamport is $C_i(t+\mu)-C_j(t)\gt0$ or $C_i(t+\mu)\gt C_j(t)$ which can be re-written $$C_i(t+\mu) - C_i(t)\gt C_j(t) - C_i(t) \tag{*}\label{*}$$

Given Lamport's previous deductions, we recognise the boundary conditions each side must satisfy namely: $$(1-\kappa)\mu \lt C_i(t+\mu) - C_i(t)$$ $$ \epsilon \gt C_j(t) - C_i(t)$$

Now, Lamport wants to find out the range of values for 'variables' $\epsilon,\kappa$ ($\mu$ is fixed) that will ensure the strict inequality $\eqref{*}$. Obviously, for real numbers (Lamport's starting assumption) if $x \lt A$ and $y \gt B$, then as long as $y \leq x$ we know $A\gt B$.

In other words, as long as $\epsilon \leq (1-\kappa)\mu$ then $\eqref{*}$ is true and so $$C_i(t+\mu)-C_j(t)\gt0$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.