Replication strategies in DBMS Theory - Time & Space Complexity

Time Complexity: Replication strategies

O(r)

Understanding Time Complexity

Replication strategies in databases help copy data across servers to improve availability and reliability.

We want to understand how the time to replicate data grows as the amount of data increases.

Scenario Under Consideration

Analyze the time complexity of this simple replication process.

-- Pseudocode for synchronous replication
BEGIN TRANSACTION;
INSERT INTO master_table VALUES (...);
FOR EACH replica IN replicas LOOP
  SEND data TO replica;
  WAIT for replica ACKNOWLEDGEMENT;
END LOOP;
COMMIT TRANSACTION;

This code inserts data into the master database and sends it to each replica, waiting for confirmation before finishing.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Sending data and waiting for acknowledgement to each replica.
• How many times: Once per replica, so the number of replicas determines repetitions.

How Execution Grows With Input

As the number of replicas grows, the time to complete replication grows roughly in direct proportion.

Input Size (number of replicas)	Approx. Operations
10	10 sends and waits
100	100 sends and waits
1000	1000 sends and waits

Pattern observation: Doubling replicas roughly doubles the replication time.

Final Time Complexity

Time Complexity: O(r)

This means the replication time grows linearly with the number of replicas.

Common Mistake

[X] Wrong: "Replication time stays the same no matter how many replicas there are."

[OK] Correct: Each replica requires sending data and waiting, so more replicas mean more total time.

Interview Connect

Understanding how replication time grows helps you design systems that stay fast and reliable as they scale.

Self-Check

What if replication was asynchronous and did not wait for acknowledgements? How would the time complexity change?