Distributed transactions and 2PC in DBMS Theory - Time & Space Complexity

Time Complexity: Distributed transactions and 2PC

O(n)

Understanding Time Complexity

Distributed transactions involve coordinating multiple databases to complete a task. Analyzing time complexity helps us understand how the coordination effort grows as more databases join.

We want to know how the time to complete a transaction changes when more participants are involved.

Scenario Under Consideration

Analyze the time complexity of the two-phase commit (2PC) protocol steps.

-- Coordinator sends prepare request to all participants
FOR EACH participant IN participants LOOP
  SEND 'prepare' TO participant;
END LOOP;

-- Participants respond with vote
FOR EACH participant IN participants LOOP
  RECEIVE vote FROM participant;
END LOOP;

-- Coordinator sends commit or abort based on votes
FOR EACH participant IN participants LOOP
  SEND 'commit' OR 'abort' TO participant;
END LOOP;

This code snippet shows the coordinator communicating with each participant in three phases: prepare, vote collection, and final decision.

Identify Repeating Operations

Identify the loops that repeat communication with participants.

• Primary operation: Sending and receiving messages to/from each participant.
• How many times: Each participant is contacted three times (prepare, vote, commit/abort).

How Execution Grows With Input

As the number of participants increases, the total communication steps increase proportionally.

Input Size (n)	Approx. Operations
10	30 messages (3 x 10)
100	300 messages (3 x 100)
1000	3000 messages (3 x 1000)

Pattern observation: The total communication grows linearly as the number of participants increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the transaction grows directly in proportion to the number of participants involved.

Common Mistake

[X] Wrong: "Adding more participants won't affect the transaction time much because messages are sent quickly."

[OK] Correct: Each participant adds extra communication steps, so more participants mean more messages and longer total time.

Interview Connect

Understanding how distributed transactions scale helps you explain coordination costs in real systems. This skill shows you grasp how multiple parts work together and affect performance.

Self-Check

"What if the coordinator could send messages to all participants at the same time? How would that change the time complexity?"