Logical Clock

Idea

• In a seminal paper, Lamport showed that although clock synchronization is possible, it need not be absolute.

• If two processes do not interact, it is not necessary that their clocks be synchronized.

• What usually matters is not that all processes agree on exactly what time it is, but rather that they agree on the order in which events occur.

Happens-before

• $a \rightarrow b$ is read "event $a$ happens before event $b$".

  • It means that all processes agree that first event $a$ occurs, then afterward, event $b$ occurs.

• The happens-before relation can be observed directly in two situations:

  • If $a$ and $b$ are events in the same process, and $a$ occurs before $b$, then $a \rightarrow b$ is true.

  • If $a$ is the event of a message being sent by one process, and $b$ is the event of the message being received by another process, then $a \rightarrow b$ is also true. A message cannot be received before it is sent, or even at the same time it is sent, since it takes a finite, nonzero amount of time to arrive.

• Happens-before is a transitive relation

  • If $a \rightarrow b$ and $b \rightarrow c$, then $a \rightarrow c$.

• If two events, $x$ and $y$, happen in different processes that do not exchange messages (not even indirectly via third parties), then $x \rightarrow y$ is not true, but neither is $y \rightarrow x$

  • These events are said to be concurrent, which simply means that nothing can be said (or need be said) about when the events happended or which event happended first.

Logical Time

• Let $C(a)$ be the logical time of an event a (that all processes agree).

• If $a \rightarrow b$, then $C(a) < C(b)$.

• The clock time, $C$, must always go forward (increasing), never backward (decreasing).

  • Corrections to time can be made by adding a positive value, never by subtracting one.

Lamport's Algorithm

• Time only moves forward.

• If a message was sent at time 60 but received at time 56, the receiver's clock must be adjusted.

• To implement Lamport's logical clocks, each process $P_i$ maintains a local counter $C_i$.

  • Before executing an event (i.e., sending a message over the network, delivering a message to an application, or some other internal event), $P_i$ does C_i += 1.

  • When process $P_i$ sends a message $m$ to process $P_j$, it sets $m$'s timestamp ts(m) = C_i after having executed the previous step.

  • Upon the receipt of a message $m$, process $P_j$ adjusts its own local counter as C_j = max(C_j, ts(m)) after which it then executes the first step and delivers the message to the application.

Example: Total-ordered Multicasting

• For example, to improve query performance, a bank may place copies of an account database in two different cities, say New York and San Francisco.

• A query is always forwarded to the nearest copy.

• Each update operation must be carried out at each replica.

• But we must solve the inconsistent update problem.

  • Assume a customer in San Francisco wants to add $100 to his account, which currently contains $1,000.

  • At the same time, a bank employee in New York initiates an update by which the customer's account is to be increased with 1 percent interest.

  • Now we have two updates: "deposit" (update 1) and "interest" (update 2).

  • If "deposit" is carried out before "interest", the account total becomes $1,111; if "interest" is carried out before "deposit", the account total becomes $1,110.

  • Consequently, the San Francisco database will record a total amount of $1,111, whereas the New York database records $1,110.

• The important issue is that both copies should be exactly the same.

• In general, situations such as these require a total-ordered multicast, that is, a multicast operation by which all messages are delivered in the same order to each receiver.

• Lamport's logical clocks can be used to implement total-ordered multicasts in a completely distributed fashion.

  • When a process receives a message:

    • It puts the message in a local queue, ordered by its timestamp.

    • It multicasts an acknowledgement to the other processes.

  • A process delivers a queued message to its application

    • Only when that message is at the head of the queue and has been acknowledged by each other process.

    • All processes have the same copy of the local queue, and all messages are delivered in the same order everywhere.