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