educative.io

Can someone elaborate a little on the quorum rules and how they ensure the claims?

Courses
,
#1

In the reading it says:

Vr + Vw > V guarantees that a data item is not read and written by two operations concurrently, but how is that? As in, how does this inequality ensure that?

It also states that the rules Vw > V / 2 ensures that at least one node receives both of the two write operations and imposes an order on them. This means that two write operations from two different operations cannot occur concurrently on the same data item. Again, I don’t understand how this inequality translates to that guarantee.

Could anyone elaborate a little?

3 Likes
#2

@Issac_Torres did you understand what does it means?
@Fahim_Omar_Ismael

#3

Giving an example might help.

Say you have a total number of nodes V = 5. Then:

  • then if your read quorum is Vr = 3, your write quorum needs to be at least Vw > 2 in order to satisfy Vr + Vw > V. Now if you try and select from an overall group of 5 nodes, 2 groups one having 3 nodes and one having 2 nodes, you will realise that you will necessarily have to select at least one node more than once. So, one node will belong to both Vr and Vw.
  • you can follow the same logic in an example where V = 5, and Vw needs to be at least Vw > 2. If you select 2 separate groups with 3 nodes each, one node will need to belong in both groups.
#4

Hi @Tausif @Isaac_Torres !!
The inequalities you’re referring to are related to the quorum-based approach in distributed systems, particularly in the context of ensuring consistency and coordination among different nodes. Let’s break down these concepts for a clearer understanding:

Vr + Vw > V

Here, V is the total number of nodes in the system, Vr is the read quorum, and Vw is the write quorum. The inequality Vr + Vw > V ensures that the sets of nodes involved in any read and write operation overlap. This overlap is crucial for maintaining consistency across the system.

  • How It Works: Imagine a system with 5 nodes (V = 5). If you have a read quorum (Vr) of 2 and a write quorum (Vw) of 4, then Vr + Vw = 2 + 4 = 6, which is greater than V (5). This means that at least one node must participate in both read and write operations. Why is this important? Because if a write operation has occurred, at least one node that knows about this new write must be involved in a subsequent read operation, ensuring that reads always get the most recent write.

  • Ensuring No Concurrent Reads and Writes: This inequality prevents a scenario where a read and a write operation can occur entirely independently without any node being aware of both operations. It guarantees that a read operation following a write operation will always reflect that write, thereby maintaining consistency.

Vw > V / 2

This rule ensures that write quorums overlap with each other. By requiring that the size of the write quorum (Vw) be greater than half the total number of nodes (V), it is guaranteed that two different write operations will have at least one node in common.

  • How It Works: Continuing with the example where V = 5, if Vw > 5 / 2, then Vw must be at least 3. If two separate write operations occur, each involving at least 3 nodes, there must be at least one node common to both operations. This common node helps in ordering the write operations and maintaining a consistent state across the system.

  • Preventing Concurrent Writes: Since every write quorum overlaps with every other write quorum, it is impossible for two writes to occur completely independently. There will always be at least one node that knows about both writes, and this helps in resolving any conflicts and ensuring that the system does not accept conflicting updates.

In summary, these inequalities are fundamental in quorum-based distributed systems for ensuring that all nodes in the system can agree on the state of the data, even in the presence of concurrent operations. This is a key aspect of achieving consistency in distributed databases and other similar systems.
I hope it helps. Happy Learning :blush:

#5

Hi @Isaac_Torres !
Your example is a good illustration of the concept, but it needs a slight adjustment to correctly reflect the quorum rules.

Let’s reframe your example with the correct numbers:

Example Scenario:

Assume you have a total number of nodes ( V = 5 ).

  1. Read Quorum (Vr): Suppose you choose a read quorum ( Vr = 3 ). This means any read operation needs to get approval from at least 3 nodes.

  2. Write Quorum (Vw): According to the rule ( Vr + Vw > V ), if ( Vr = 3 ), then ( Vw ) needs to be more than ( 2 ) (since ( V = 5 )), to satisfy the inequality. The smallest integer greater than 2 is 3, so ( Vw ) should be at least ( 3 ).

    • This ensures that during any write operation, at least 3 nodes (out of 5) participate.

Analysis:

  • Overlap in Read and Write Quorums: With ( Vr = 3 ) and ( Vw = 3 ), there’s an overlap guaranteed. For instance, if you select 3 nodes for a read operation and another 3 for a write operation, there must be at least one node that is common between these two sets. This is because you’re selecting more than half of the total nodes (5) for each operation.

  • Ensuring Consistency: This overlap ensures that a node that participated in the most recent write is also involved in the read operation, hence the read operation reflects the latest write.

  • Write Quorum Overlap: According to the rule ( Vw > V / 2 ), with ( V = 5 ), the write quorum ( Vw ) should be more than ( 2.5 ), which means ( Vw ) must be at least ( 3 ). If two separate write operations happen, each involving at least 3 out of the 5 nodes, there’s guaranteed to be at least one node that’s common to both operations. This common node helps in maintaining a consistent order of writes.

Your example correctly demonstrates the concept, with the adjustment that both the read and write quorums need to be at least 3 in a system with 5 nodes to ensure the necessary overlap for consistency and order. The key takeaway is that these quorum sizes ensure that there is always a node that participates in both read and write operations, thus maintaining the consistency of the data across the distributed system.
Happy Learning :blush: