6
$\begingroup$

In the timepiece (excuse the pun) that is Time, Clocks and the Ordering of Events, Lamport describes the logical clock algorithm as the following:

  1. Each process $Pi$ increments $Ci$ between any two successive events.
  2. If event a is the sending of a message m by process $Pi$, then the message $m$ contains a timestamp $Tm = Ci(a)$.
  3. Upon receiving a message $m$, process $Pi$ sets $Ci$ greater than or equal to its present value and greater than $Tm$.

However, the algorithm as it is described on Wikipedia (and other websites) is a little different:

  1. A process increments its counter before each event in that process.
  2. When a process sends a message, it includes its counter value with the message.
  3. On receiving a message, the receiver process sets its counter to be greater than the maximum of its own value and the received value before it considers the message received.

This leaves me with the following questions:

  1. Should be increment the counter before sending a message, as the sending of a message is itself an event. This incremented timestamp is the value that is sent with the message.
  2. When a message is received by process $Pi$ Lamport states that $Pi$ logical clock should be set to $max(Tm + 1, Ci)$. However, the Wikipedia article says that this should be $max(Tm, Ci) + 1$. Is Wikipedia wrong?
$\endgroup$
2
$\begingroup$

Considering that any local action (e.g. increasing a counter) done by a process is an event, the Wikipedia sentence

"A process increments its counter before each event in that process."

does not make any sense to me. Let me try to answer your questions:

  1. Should we increment the counter before sending a message, as the sending of a message is itself an event. This incremented timestamp is the value that is sent with the message.

Both actions (i.e. increasing the counter and sending the message) happen atomically in the same event. The same is true when a message is received: The receive event already includes the counter update.

  1. When a message is received by process Pi Lamport states that Pi logical clock should be set to max(Tm+1,Ci). However, the Wikipedia article says that this should be max(Tm,Ci)+1. Is Wikipedia wrong?

Note that, according to Lamport's paper, the logical clocks must satisfy the following property:

If $a$ happens before $b$ then $C(a) < C(b)$.

In particular, this means that clock values (of events) at the same process must be strictly increasing. Therefore, the correct update rule is $\max(Tm,Ci)+1$, as otherwise two subsequent events at the same process might have the same value.

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