Lamport Clocks

• In a distributed system, there is no global time and no global state \(\implies\) the clock of different nodes in a distributed system can have different values.

• Happened-before Relationship:

  • Some events in a distributed system happened before other events and others are concurrent

  • Happened-before is a partial ordering on events in a distributed system:

    Given events \(E1, E2, E3\) and \(E1\) happens before \(E2\) and \(E1\) happens before \(E3\), we have \(E2\) and \(E3\) are concurrent and \(E1 < E3\) and \(E1 < E3\).

• \(\rightarrow\) relation satisfies the following conditions:

  1) If \(a\) and \(b\) are events in the same process, and \(a\) comes before \(b\), then \(a \rightarrow b\)

  2) If \(a\) is the sending of a message by one process and \(b\) is the receipt of the same message by another process, then \(a \rightarrow b\)

  3) If \(a \rightarrow b\) and \(b \rightarrow c\), then \(a \rightarrow c\)

• Two distinct events \(a\) and \(b\) are said to be concurrent if \(a \not\rightarrow b\) and \(b \not\rightarrow a\)

• Logical Clocks:

  • Assigns a monotonically increasing number \(C(x)\) for each event \(x\) in a process
  • If event \(x\) happens before event \(y\), \(C(x) < C(y)\) (Note, \(C(x) < C(y) \not\implies x < y\))
  • If \(x\) and \(y\) are in the same process, and \(x < y\), then \(C(x) < C(y)\)
  • If \(x\) is sending of message, and \(y\) receipt of the message, then \(x < y\) and \(C(x) < C(y)\)

• Implementing Logical Clocks:

  • Within a process \(X\), increment \(C(x)\) every time an event happens
  • When process \(X\) receives a message with timestamp \(T\), \(C(x) = \max(T, C(x)) + 1\)

• How do we break the tie of the concurrent events and achive total ordering of the events in the sytem:

  • If \(x\) and \(y\) in same process, and \(x < y\), \(C(x) < C(y)\)
  • If \(x\) and \(y\) are concurrent (\(x = y\)), then \(P(x) < P(y) \implies C(x) < C(y)\) (\(P(\cdot)\) means process ID)

Vector Clocks

• Limitation of Lamport Clocks:

  • If \(C(x) < C(y)\), we cannot tell whether \(x < y\)
  • We can only say if \(x < y\), then \(C(x) < C(y)\)

• Goal: to enable each process to have an approximation of global time at all processes (Every message propagates info about state of whole system)

• Each process has a vector of clocks:

  • Clock \(C_i\) is time for process \(i\) as seen by the owner of the vector
  • \(C_i\) in two different vectors may not be the same

• Implementing Vector Clocks:

  • Each process \(P_i\) updates its component \(C_i\) in its vector clock (This update happens for each internal event (e.g. on receiving a message))
  • Each message has a vector clock time stamp
  • On getting the message, for each field \(x\) in the vector: \(C[x] = \max(C[x], message\_time\_stamp[x])\)

• Comparing Vector Timestamps:

  • Timestamp \(X \le Y\) if all components of \(X \le\) corresponding components in \(Y\)
  • Timestamp \(X < Y\) if at least one component is strictly lesser, with all others being equal
  • Otherwise, \(X\) and \(Y\) are concurrent