---
title: "Vector clock synchronization algorithm"
subject: "Distributed System"
chapter: 5
key: "semester_7/distributed_system:vector-clock-algorithm"
source: https://www.bctengineer.com/q/semester_7/distributed_system/vector-clock-algorithm
site: BCT Engineering
---

# Vector clock synchronization algorithm

Distributed System · Chapter 5: Time and State in Distributed Systems

- Asked in: 2074 Asoj, 2+6 marks; Model question (asked 2 times)
- Video: [Vector Clock 🔥🔥](https://www.youtube.com/watch?v=Q69Thj9vFw4) — Perfect Computer Engineer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/vector-clock-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-5

## Question

Why is clock synchronization necessary? Explain the clock synchronization algorithm using vector clock along with an example. (Define vector clock.)

## Short answer

Clock synchronization is needed because clocks drift and events must be ordered consistently. A vector clock is a vector of N counters per process that captures causality exactly: increment own entry on local events, attach vector on send, take element-wise maxima on receive, then increment own entry. Events are concurrent if neither vector is smaller than the other.

## Answer

#### Why clock synchronization is necessary
Each machine has its own clock, and clocks drift (about 10⁻⁵ to 10⁻⁶ s/s). Without agreement, events recorded on different machines cannot be ordered correctly. Needed for: ordering of transactions and log entries, distributed mutual exclusion and deadlock detection, replica consistency, authentication tickets with expiry, and debugging. When real time is not important but order is, logical clocks such as vector clocks are used.

#### Vector clock
A vector clock is a logical clock where each of N processes keeps a vector VCi of N integers. VCi[i] counts local events of Pi, and VCi[j] is the number of events of Pj that Pi knows about. It captures causality exactly.

#### Algorithm
1. Initially VCi[j] = 0 for all j.
2. For each local event, Pi increments VCi[i] by 1.
3. On sending a message, Pi increments VCi[i] and attaches a copy of VCi as timestamp t.
4. On receiving a message with t, Pi sets VCi[j] = max(VCi[j], t[j]) for all j, then increments VCi[i].

Comparison: V(a) < V(b) if every V(a)[k] ≤ V(b)[k] and at least one is smaller. Then a → b. If neither vector is smaller, the events are concurrent.

#### Example with three processes
```text
 P1: a(1,0,0) b(2,0,0)               e(3,3,0)
                  \                  ^
 P2: c(0,1,0)      d(2,2,0)--g(2,3,0)-+
 P3: f(0,0,1)
```
- a, b: events at P1 giving (1,0,0), (2,0,0); b sends m1 with (2,0,0).
- c: local event at P2, (0,1,0).
- d: P2 receives m1: max((0,1,0),(2,0,0)) = (2,1,0), then own entry +1 gives (2,2,0).
- g: P2 sends m2 with (2,3,0).
- e: P1 (at (2,0,0)) receives m2: max = (2,3,0), own entry +1 gives (3,3,0).
- f: local event at P3, (0,0,1).

Observations: b (2,0,0) < d (2,2,0), so b → d. c (0,1,0) and a (1,0,0) are incomparable, so concurrent. f (0,0,1) is concurrent with all P1 and P2 events shown.

Compared with Lamport clocks, vector clocks show both causality and concurrency, at the cost of vectors of size N in every message.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In a vector clock, what does VCi[j] (j different from i) represent?
   A. The number of messages Pi sent to Pj
   B. The real time at Pj
   C. The number of events at Pi
   D. The number of events at Pj that Pi knows about
   Answer: D. VCi[i] counts own events; other entries record Pi's knowledge of others. (Key point: Meaning of VCi[j])

2. P2 has (0,1,0) and receives a message with (2,0,0). What is P2's new vector?
   A. (2,2,0)
   B. (2,1,0)
   C. (2,0,0)
   D. (0,2,0)
   Answer: A. Max gives (2,1,0), then increment own entry: (2,2,0). (Key point: Receive example)

3. Events a with (1,0,0) and c with (0,1,0): what is their relation?
   A. a happened before c
   B. Concurrent
   C. c happened before a
   D. They are the same event
   Answer: B. Neither vector is smaller than the other. (Key point: Concurrency)

4. Why are vector clocks preferred over Lamport clocks for causality?
   A. They need no message timestamps
   B. They use less memory
   C. V(a) < V(b) holds if and only if a happened before b
   D. They synchronise real time
   Answer: C. Vector clocks capture causality exactly, in both directions. (Key point: Why vector better)

## Related in Distributed System

- [Physical clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-sync-algorithm) — Distributed System, chapter 5
- [Need of logical clock synchronization](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alogical-clock-sync-need) — Distributed System, chapter 5
- [Clock synchronization need; Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aclock-sync-lamport-need) — Distributed System, chapter 5
- [Problems of Lamport's clock; vector clock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-problems-vector-clock) — Distributed System, chapter 5, asked 2×
- [Lamport's logical clock algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-clock) — Distributed System, chapter 5, asked 5×
- [Cristian's algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acristian-algorithm) — Distributed System, chapter 5, asked 3×

## Related in other subjects

- [Clock synchronization in DFS](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Aclock-synchronization-dfs) — Big Data Technologies, chapter 1
- [CST steel plate: stiffness, load vector, displacements](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acst-stiffness-load-displacement-c8) — Computational Techniques in Civil Engineering, chapter 4
- [Condition for constant direction of vector](https://www.bctengineer.com/question.md?key=semester_2%2Fmathematics%3Acondition-constant-direction-vector) — Mathematics, chapter 5, asked 6×
- [Condition for constant magnitude of vector](https://www.bctengineer.com/question.md?key=semester_2%2Fmathematics%3Acondition-constant-magnitude-vector) — Mathematics, chapter 5, asked 5×