Sentinel quorum concept in Redis - Time & Space Complexity

Time Complexity: Sentinel quorum concept

O(n)

Understanding Time Complexity

When Redis Sentinel monitors servers, it needs to decide when enough Sentinels agree that a server is down. This agreement is called a quorum.

We want to understand how the time to reach this quorum grows as the number of Sentinels increases.

Scenario Under Consideration

Analyze the time complexity of the following Redis Sentinel quorum check.

// Pseudocode for quorum check
int votes = 0;
for each sentinel in sentinels {
  if (sentinel reports server down) {
    votes++;
  }
}
if (votes >= quorum) {
  mark server as down;
}
    

This code counts how many Sentinels say the server is down and compares it to the quorum number.

Identify Repeating Operations

We look for repeated steps in the code.

• Primary operation: Looping through all Sentinels to check their votes.
• How many times: Once for each Sentinel in the system.

How Execution Grows With Input

As the number of Sentinels grows, the time to count votes grows too.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The number of checks grows directly with the number of Sentinels.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide if the quorum is reached grows in a straight line as more Sentinels join.

Common Mistake

[X] Wrong: "The quorum check happens instantly no matter how many Sentinels there are."

[OK] Correct: Each Sentinel's vote must be checked one by one, so more Sentinels mean more work.

Interview Connect

Understanding how quorum checks scale helps you explain how distributed systems keep data safe and available as they grow.

Self-Check

"What if Sentinel votes were stored in a data structure that allows instant counting? How would that change the time complexity?"