Vector Clock

• Wikipedia: https://en.wikipedia.org/wiki/Vector_clock
• First: NO_ITEM_DATA:matternVirtualTimeGlobal and Timestamps in message-passing systems that preserve the partial ordering. Colin J. Fidge. 1987
• Youtube: https://www.youtube.com/watch?v=x-D8iFU1d-o

Let the system consist of \(n\) nodes.

1. Each node \(i\) maintains an array \(VC_{i} = [0,\ldots,0]\).
2. For every local event at node \(i\), it updates its local clock, i.e., \(VC_{i}[i] += 1\).
3. While sending a message \(m\):
   1. Send \((VC_{i}, m)\)
   2. \(VC_{i}[i] += 1\)
4. On receiving a message \((VC_{j}, m)\):
   1. \(VC_{i}[i] += 1\)
   2. If \(VC_{i}[j] \le VC_{j}[j]\), \(VC_{i}[j] = VC_{j}[j] + 1\)
   3. For \(k \in [1,n]\): \(VC_{i}[k] \leftarrow max(VC_{i}[k],VC_{j}[k])\)

• Step 2 is needed to prevent local events from being assigned the same time.
• Step 3b is needed to prevent the sending event from being assigned the same time as the previous event.
• Step 3a is needed to ensure that the recipient updates the clock of other nodes to ensure that \(L(a) < L(b) \Rightarrow a \rightarrow b\)
• Step 4a is needed to prevent the receiving event from being assigned the same time as a future local event.
• Step 4b does not appear to be needed (according to Wikipedia and Mattern et al.)
• Step 4c ensures the uniqueness of the logical clock

• From Mattern et al., at any instant of real time, \(\forall i,j\): \(VC_{i}[i] \ge VC_{j}[i]\)
• (Mattern et al.) Define a total order for two events \(e\) and \(e'\) as follows:
  • \(e \le e'\) iff \(\forall i: e[i] \le e'[i]\)
  • \(e < e'\) iff \(e\le e'\) and \(e\ne e'\), and
  • \(e || e'\) iff \(\neg (e

• Timestamps in message-passing systems that preserve the partial ordering. Colin J. Fidge. 1987 Debugging distributed logs
• Timestamps in message-passing systems that preserve the partial ordering. Colin J. Fidge. 1987 This paper talks about an application where users send requests to access data in a distributed database by providing ranges of timestamps. If the servers cross the timestamp in the request the server considers the request as timed out.
• NO_ITEM_DATA:matternVirtualTimeGlobal Computing global state (like a snapshot) on distributed systems without FIFO channels