0
$\begingroup$

In Lamport's paper, Time, Clocks, and the ordering of Events in a Distributed System he says that the converse of the clock condition does not hold and if it did, we could expect concurrent events to occur at the same time. I am not sure how he arrives at this conclusion.

The Clock Condition is:

For any events a, b in a distributed system: if a -> b then C(a) < C(b).

The converse does not hold: if C(a) < C(b) then a -> b.

Where C(n) assigns a logical clock number to any event in the system. Logical clock numbers monotonically increasing values for each process in the system and two conditions hold in order for partial orderings given that the clock condition is true:

  1. if a and b are both events in a process P_i and a comes before b, then C_i(a) < C_i(b)

  2. if a is a sending event in P_i and b is a receiving event in P_j then C_i(a) < C_j(b).

Intuitively I can see why the converse does not hold. It is possible in the system of logical clocks that C(a) < C(b) when we do not have a partial ordering that guarantees the relation a -> b. But I have no clue why the converse being true would imply that any two concurrent events occur at the same time.

$\endgroup$

1 Answer 1

1
$\begingroup$

Assume the clock condition AND its converse: $$C(a)\lt C(b) \Rightarrow a \rightarrow b \tag{*}\label{*}$$

Next, take note that $\neg(a \rightarrow b)$ implies either $b \rightarrow a$ or $a \nrightarrow b$ (i.e. if '$a$ does NOT happen before $b$' then either '$b$ happens before $a$' or they are concurrent events).

Now, since the implication $\eqref{*}$ is (assumed) true, its contrapositive must also be true: $$\neg(a \rightarrow b) \Rightarrow C(a)\geq C(b)$$

Applying our negation rule, we find either $b \rightarrow a \Rightarrow C(a)\geq C(b)$ (which reduces to the clock condition) or $$a \nrightarrow b \Rightarrow C(a)\geq C(b)$$

Lamport is only interested in the latter case: "...we cannot expect the converse condition to hold as well, since that would imply that any two $\mathbf{concurrent}$ events must occur at the same time."

To show this, remember Lamport said when $a,b$ are concurrent then both $a \nrightarrow b$ and $b \nrightarrow a$ so $$b \nrightarrow a \Rightarrow C(b)\geq C(a)$$ The last two equations imply if $a$ and $b$ are concurrent, $C(a)=C(b)$.

To derive the contradiction, take any two events $a, b$ concurrent but on separate processes. Then their clock numbers must be the same. Now if there is another concurrent event before or after $a$ (on the same process), then it too must have the same clock number as $b$ and therefore $a$. But that contradicts the clock condition (e.g. see condition C1 in the paper).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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