3
$\begingroup$

In lamport's paper1, he define global local timestamp, which is composed of process id and local lamport timestamp.

This timestamp is used to order all the events in a distributed system.

enter image description here

The rule to compare two events is following.

enter image description here

My Question

Imagine we have two events, one happens in process 1 (P1), with local timestamp 9, another event happens in process 2 (P1), with identical timestamp 9.

Based on lamport's rule, the first one is earlier than second one.

C1(9) => c2(9)

But why?

From my understanding, it does't make sense. An event is treated earlier just because it is born in a process which has smaller pid?

Reference

  1. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System.”
$\endgroup$
0

1 Answer 1

3
$\begingroup$

No, "it doesn't make sense". You are correct in the sense that that choice is not a logical consequence of any requirements and known truths. It could be considered as arbitrarily selected.

Well, we do not need to make any sense when we are forced to decide which one of two global timestamps, $(T_i,i)$ and $(T_j,j)$ where $T_i=T_j$, is earlier than the other one, as long as our choices are consistent, so that we will be able to arrive at a total ordering that respects the local ticks. There are indeed many different ways to decide that can lead to many different total orderings.

What does it mean by "choice being consistent"? Here is a simple example. Suppose we have three global timestamps, (1,5), (1,2), (1,4). It is consistent if we decide (1,5) $\prec$ (1,2), (1,2) $\prec$ (1,4), (1,5) $\prec$ (1,4). However, it is not consistent if we decide (1,5) $\prec$ (1,2), (1,2) $\prec$ (1,4), (1,4) $\prec$ (1,5). Intuitively, if (1,5) precedes (1,2) and (1,2) precedes (1,4), then (1,5) must precedes (1,4). That is, the transitivity of $\prec$ must be respected; otherwise, $\prec$ is not a partial ordering any more. The transitivity of temporal ordering of events is the essence of time.

Among many schemes to decide which global timestamp is earlier in a pair of two global timestamps with the same local timestamp, the easiest and most natural one is the one specified in the paper. That is, $(T_i,i) \prec (T_j,j)$ where $T_i=T_j$ and $i<j$. Since we have assumed that the second coordinate, the process number is globally unique, this scheme is complete in the sense that all those kind of pairs are ordered and this scheme is apparently consistent. Moreover, whenever the process numbers do have any inkling to the actual order of physical time as what happens in many situations, smaller process number usually indicates earlier in physical time. So, after all, that decision in the paper makes a lot of sense.

$\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.