# Time

**Physical time**: is measured by physical clocks which *tick* with a certain rate

**Logical time**: is measured by logical clocks which *tick* when events occur

**Clock skew**: the difference in timing between two or more clocks in a distributed system

## Physical clocks #

Measure real world time

**Perfect**clock: $C(t)$**Correct**clock $C_i(t)$: $C_i(t)= C(t)$**Accurate**clock $C_i(t)$: $dC_i(t)/dt = 1$**Synchronized**clocks $C_i(t)$ and $C_k(t)$ at time $t$: $C_i(t) = C_k(t)$

Measuring between local events: no synchronization required, however clock should be sufficiently accurate

Measuring between events on two different systems: clocks should be synchronized but don't need to be current, and sufficiently accurate

**Clock synchronization**: each system $i$ calculates its clock based on the distributed values by a function $f$. $$ c_i(t) = f(C_j, C_k) $$

**Coordinated Universal Time (UTC)**: the primary time standard that regulates clocks and time worldwide.**Maximum clock skew $\delta$ (seconds)**: how much difference you allow to occur within the system.**Maximum drift rate $c$**: crystal clocks are not perfect, determinates the maximum error from "real time".

Both determine the frequency of clock synchronization, resynchronization should happen at least every $\delta/2c$ if clocks should not be more than $\delta$ apart.

### Cristian's Clock Synchronization algorithm #

There is a master server that has a UTC receiver. Slave servers query master server (at least every $\delta/2c$ seconds) and then updates it clock by **estimating** the masters current time ($C_M'$) after receiving response: $$ C_M'(T_1) = C_M + P\ $$ $$ P = (T_1 - T_0 - I) / 2 $$ where $C_M$ is the masters time, $T_0$ is the time of the request, $T_1$ the time of the response and $I$ the interrupt handling time.

More exact estimations can be done by performing multiple measurements and ignoring the measurements where $T_1 - T_0$ exceeds a certain threshold. The software clock can be slowed down without breaking by letting some interrupts pass.

### Lamport's Clock Synchronization algorithm #

There is no "master" time, instead time servers periodically exchange information. If a process sends a message the timestamp is added, if a message is received the clock is set to max (received timestamp + minimum of propagation delay, own clock value). Modelled as a directed graph (with diameter $d$, the longest, shortest path between two vertices) A message is sent at least every $\tau$ seconds on one edge of the graph.

Under assumptions, $\delta \approx d(2c\tau + z)~~ \forall t \geq t_0 + \tau d$

## Logical clocks #

Logical clocks provide a consistent ordering of events in distributed system without using actual time. They are used in a wide range of distributed algorithms like mutual exclusion, replication and deadlock detection.

## Causal dependencies #

**Causal / $a$ happens before $b$:** strict partial order $a \rightarrow b$

- $a$ is executed before $b$ in the same process: $a \rightarrow b$
- $a$ sends a message to $b$: $a \rightarrow b$
- let $a$, $b$ and $c$ be events in any process, if $a \rightarrow b$ and $b \rightarrow c$, then $a \rightarrow c$ (transitivity)

**Concurrent / causally unrelated** $a\ ||\ b$: $\neg (a \rightarrow b) \land \neg (b \rightarrow a)$

### Scalar clocks #

Each process keeps a clock which starts at 0, on a event or send the clock value is increased by one

Scalar clock condition, a system of scalar clocks is correct when: $$ \forall a, b, : a \rightarrow b \Rightarrow C(a) < C(b) $$

### Synchronization algorithm #

- Initialization $C(p_i) := 0$
- Local event / send: $C(p_i) := C(c_pi) + 1$
- Receive: $C(p_i) := \max(C(c_pi),C(m')) + 1$

### Lamports Distributed Mutual Exclusion Algorithm #

- Every process has a request queue (RQ) that contains requests $Req(T_r: p_i)$ to lock the resource, $T_r$ is the time of the request.
- A process can lock the resource if it has a $Req(T_r : P_i)$ in its RQ before all other requests AND received a message with timestamp $> T_r$ from all other processes.
- When a resource is released $Releasse(T_j: P_i)$ is send to all other processes and the $Req$ is removed from all queues.

### Vector clocks #

The system of vector clocks is correct, when $$ \forall a, b : a \rightarrow b \Leftrightarrow VC(a) < VC(b) $$

**Vector timestamp**: $n$-dimensional vector where $n$ is the number of processes in the system

**Causal history** of event $e$: $$ \downarrow(e) = { e' \mid e'\ _r\rightarrow e } $$ $_r\rightarrow$ is the reflexive closure of $\rightarrow$ the set of events up till and including the event

Mathematical functions: $$ VC_1 \leq VC_2 \Leftrightarrow \forall i : VC_1[i] \leq VC_2[i] $$ $$ VC_1 || VC_2 \Leftrightarrow \neg (VC_1 \leq VC_2) \land \neg (VC_2 \leq VC_1) $$ $$ VC_1 < VC_2 \Leftrightarrow VC_1 \leq VC_2 \land VC_1 \neq VC_2 $$

**Supremum** (component-wise max): $$ sup(VC_1, VC_2) = \forall i : max(VC_1[i], VC_2[i]) $$

### Synchronization algorithm #

- Local event: increases own component
- Sending: increase and include value in message
- Receiving: increase own component and calculate supremum