Trait QuorumIntersection 

pub trait QuorumIntersection<Other>
where
    Self: QuorumSet,
    Other: QuorumSet<Id = Self::Id>,
{
    // Required method
    fn intersects_with(&self, other: &Other) -> Option<bool>;
}

Relation between quorum sets whose quorums always intersect.

Quorum sets A and B have quorum intersection, written A ~ B, when: ∀ qᵢ ∈ A, ∀ qⱼ ∈ B: qᵢ ∩ qⱼ != ø. In words, every quorum in A intersects every quorum in B. Consensus protocols use this relation to make membership changes without losing overlap between old and new decisions.

The relation is symmetric, and both universal quantifiers are load-bearing: weakening either one to “some quorum” (∃) breaks safety, because a reader or a candidate cannot know which quorum is “the right one” — the overlap must hold for every quorum it may legally assemble. E.g. for write quorums {a,b}, {b,c}, {a,c} and read quorums {b,c}, {x,y}: every write quorum intersects some read quorum, yet a read using {x,y} observes no committed write.

In a Raft-style membership change, quorum intersection is one safety requirement. The protocol also has to prevent an old, smaller candidate from being elected during the transition.

Required Methods

fn intersects_with(&self, other: &Other) -> Option<bool>

Return whether every quorum of this quorum set intersects every quorum of the other quorum set.

• Some(true): the check proved that every quorum pair intersects.
• Some(false): the check proved that some quorum pair is disjoint.
• None: the check proved neither. An implementation may use a condition that is sufficient but not necessary, so failing that condition tells the caller nothing about the true relation.

Callers can act on Some(true). On Some(false) or None, they need another proof of transition safety. QuorumBridge::joint_with builds the joint used by read/write membership changes. verify_intersection computes the exact relation in exponential time.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementations on Foreign Types

impl<ID> QuorumIntersection<BTreeSet<ID>> for BTreeSet<ID>

where ID: Ord + Clone,

Exact quorum intersection for two flat majority configs.

A smallest majority of self first takes the IDs that other lacks, and then takes shared IDs only as needed. A smallest majority of other does the same. Two disjoint majorities exist exactly when the shared IDs are enough for both, so the check is exact and runs in O(n).

fn intersects_with(&self, other: &BTreeSet<ID>) -> Option<bool>

Return Some(true) when every majority of self intersects every majority of other, and Some(false) otherwise. This check never returns None.

An empty BTreeSet has no quorum, so it has quorum intersection with every config.

impl<ID> QuorumIntersection<BTreeSet<ID>> for Vec<BTreeSet<ID>>

where ID: Ord + Clone,

A joint config and a flat config are treated as having quorum intersection when some config of the joint intersects the flat config: every quorum of the joint is also a quorum of that config. This is sufficient but not necessary for that property, so this check answers None for some pairs whose quorums do in fact all intersect.

fn intersects_with(&self, other: &BTreeSet<ID>) -> Option<bool>

Return the exact answer of the flat BTreeSet check when self holds one config. For other joints, return Some(true) when some config of self intersects other.

Return Some(true) when self is empty: an empty joint has no quorum, so no pair of quorums can be disjoint.

Return None for every other pair.

impl<ID> QuorumIntersection<Vec<BTreeSet<ID>>> for BTreeSet<ID>

where ID: Ord + Clone,

Quorum intersection is symmetric, so this check returns the answer of the joint config’s check.

fn intersects_with(&self, other: &Vec<BTreeSet<ID>>) -> Option<bool>

impl<ID> QuorumIntersection<Vec<BTreeSet<ID>>> for Vec<BTreeSet<ID>>

where ID: Ord + Clone,

Two joint configs are treated as having quorum intersection when some config of one intersects some config of the other: every quorum of a joint is also a quorum of each of its configs, so every quorum of one joint then intersects every quorum of the other. This is sufficient but not necessary for that property, so this check answers None for some pairs of joints whose quorums do in fact all intersect.

fn intersects_with(&self, other: &Vec<BTreeSet<ID>>) -> Option<bool>

Return the exact answer of the flat BTreeSet check when each joint holds one config. For other joints, return Some(true) when some config of self intersects some config of other.

When either joint is empty, return Some(true): an empty joint has no quorum, so no pair of quorums can be disjoint.

Return None for every other pair: two configs that do not intersect prove nothing about two joints that contain them.

Read more about extended membership change in OpenRaft: https://docs.rs/openraft/latest/openraft/docs/data/extended_membership/index.html

Implementors

impl<ID> QuorumIntersection<ExplicitQuorumSet<ID>> for ExplicitQuorumSet<ID>

where ID: Ord + Clone,

Exact quorum intersection for two lists of minimal quorums.

Every quorum of a rule holds one of its listed quorums, and every listed quorum is a quorum. Two quorums are therefore disjoint only when two listed quorums are, so the check is exact. It runs in O(a * b * n) for a and b listed quorums of at most n IDs.

impl<ID> QuorumIntersection<GridQuorumSet<ID>> for GridQuorumSet<ID>

where ID: Ord + Clone,

Quorum intersection for two grid rules, exact when either rule is GridRule::FullRow.

A set meets every quorum of a rule exactly when the other GridRule over the same grid accepts the set:

• A set meets every row exactly when it holds an ID of every row.
• A set meets every OnePerRow quorum exactly when it holds a full row. A set without a full row misses an ID of each row, and these IDs form a OnePerRow quorum that the set misses.

Every quorum of a FullRow rule holds one of its rows, and every row is a quorum. A FullRow rule therefore intersects another rule exactly when each of its rows meets every quorum of the other rule. The check gives no answer for two OnePerRow rules. A FullRow read rule with a OnePerRow write rule over one grid, or the reverse, always gets an exact answer.

impl<ID> QuorumIntersection<HierarchicalQuorumSet<ID>> for HierarchicalQuorumSet<ID>

where ID: Ord + Clone,

Sufficient quorum intersection for two rules over the same tree.

A quorum of each rule reaches at least quorum_size members of the root group. When the two quorum sizes sum to more than the member count, two quorums reach a common member. A common ID is shared by both quorums, and a common child group repeats the argument one level down. So two quorums share an ID when the two quorum sizes of every group sum to more than its member count. The dual() of a rule gives every group the quorum size that makes this sum exceed its member count by exactly 1, so the check proves every rule against its dual. The check runs in O(n).

impl<ID> QuorumIntersection<ThresholdQuorumSet<ID>> for ThresholdQuorumSet<ID>

where ID: Ord + Clone,

Exact quorum intersection for two threshold rules.

A smallest quorum of self first takes the IDs that other lacks, and then takes shared IDs only as needed. A smallest quorum of other does the same. Two disjoint quorums exist exactly when the shared IDs are enough for both, so the check is exact and runs in O(n).

impl<ID> QuorumIntersection<WeightedQuorumSet<ID>> for WeightedQuorumSet<ID>

where ID: Ord + Clone,

Sufficient quorum intersection for two weighted rules.

Two disjoint sets together weigh at most the total weight. When two rules hold the same weights and their thresholds sum to more than the total weight, a quorum of one and a quorum of the other are therefore never disjoint. The check runs in O(n) for n IDs.

impl<Q> QuorumIntersection<Joint<Q>> for Joint<Q>

where Q: QuorumIntersection<Q>, Q::Id: Ord,

Two joints are treated as having quorum intersection when some rule of one intersects some rule of the other: every quorum of a joint is also a quorum of each of its rules, so every quorum of one joint then intersects every quorum of the other. This is sufficient but not necessary for that property, so this check answers None for some pairs of joints whose quorums do in fact all intersect.