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) and on None they must take the unconditionally safe path, e.g. bridge through a joint config built by QuorumBridge. 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(other.is_empty()) when self is empty: an empty joint accepts the empty set as a quorum, and the empty set misses every quorum of a non-empty other. An empty other has no quorum to miss.

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) exactly when the other joint holds an empty config. An empty joint accepts the empty set as a quorum, and the empty set misses every quorum of the other joint. A joint that holds an empty config has no quorum to miss.

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