Search IconIcon to open search


Last updated May 5, 2022 Edit Source

Measuring time in the context of computer systems

# Physical Time

Two types of clock

  1. Physical clock: number of seconds elapsed
  2. Logical clock: count events, e.g. messages sent

Time is hard! So many different ways of measuring time

Periodically adjust local clock with a server with a more accurate time source using Network Time Protocol (NTP) or Precision Time Protocol (PTP)

How do we estimate time over a network?

# Logical Time

Problem is that even with synced clocks we can have $t_2 < t_1$ with a message A at $t_1$ with a response B at $t_2$. Here, the timestamp order is inconsistent with expected order! This can happen when the clock skew is less than the one way network latency.

So we use logical clocks to work based off of the number of events that have occurred rather than actual time passed.

# Lamport Clocks

Provides a partial order on events



This means that two identical Lamport timestamps might not correspond to the same unique event. However if we include the node $N(e)$ for the node where event $e$ occurred, then $(L(e), N(e))$ uniquely identifies event $e$.

We attempt to define a total causal order

$$(a \prec b) \iff (L(a) < L(b)) \lor (L(a) = L(b) \land N(a) < N(b))$$

However even now, given timestamps $L(a) < L(b)$, we can’t tell whether $a \rightarrow b$ or $a \parallel b$

To separate causality from concurrent events, we need vector clocks!

# Vector Clocks

Provides a causal order on events

Instead of having a single counter t for all nodes, we keep a vector timestamp $a$ of an event for each node so we have $V(a) = \langle t_1, t_2, \ldots, t_n \rangle$ where $t_i$ is the number of events observed by node $N_i$

Each node has a current vector timestamp $T$, on an event on node $N_i$, increment vector element $T[i]$


Thus, a vector timestamp of an event $e$ actually represents all of its causal dependencies: ${ e } \cup {a | a \rightarrow e }$

E.g. $\langle 2, 2, 0 \rangle$ represents first two events from $N_1$, first two events from $N_2$, and no events from $N_3$


Properties (based on Order theory)

You can tell that versions are in conflict when neither vector clock “descends” from the other. In order for vector clock B to be considered a descendant of vector clock A, each marker in vector clock A must have a corresponding marker in B that has a revision number greater than or equal to the marker in vector clock A. Markers not contained in a vector clock can be considered to have revision number zero.

Vector Clock Example

# Hybrid Logical Clocks

Physical and logical clocks both have non-ideal properties.

Note that this is not a substitute for Vector Clocks as they only provide partial order instead of causal order

Can we combine them to achieve better properties?

Hybrid Logical Clocks (HLCs) achieve

We can store a tuple containing:

This tuple can be used directly as a replacement for a physical clock timestamp (and in fact works as a superposition on top of the NTP protocol without any interference)

# Pseudocode

Interactive Graph