> For the complete documentation index, see [llms.txt](https://ret2basic.gitbook.io/ctfnote/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ret2basic.gitbook.io/ctfnote/computer-science/distributed-systems/coordination/logical-clock.md).

# 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.