Struct ExplicitQuorumSet 

pub struct ExplicitQuorumSet<ID> { /* private fields */ }

A quorum rule that accepts an ID set holding every ID of one of its listed quorums.

The rule keeps only the minimal quorums. new() sorts the list, drops duplicate quorums, and drops each quorum that holds another listed quorum, because every set that holds the larger quorum also holds the smaller one. Two rules that accept the same sets therefore hold the same list.

Every accepted set holds a listed quorum, so two rules have quorum intersection exactly when every listed quorum of one meets every listed quorum of the other. The check compares each pair of listed quorums. A rule with no listed quorum accepts no set.

Listing quorums costs memory that grows with the policy. Some policies need exponentially many minimal quorums: a majority of n IDs has C(n, n/2 + 1) of them, 126 for 9 IDs and 6435 for 15.

Examples

use std::collections::BTreeSet;

use quorum_set::{ExplicitQuorumSet, QuorumIntersection, QuorumSet};

// {1,2,3} holds {1,2}, so the rule keeps only {1,2} and {3,4}.
let quorums = [BTreeSet::from([1, 2, 3]), BTreeSet::from([3, 4]), BTreeSet::from([1, 2])];
let rule = ExplicitQuorumSet::new(quorums).unwrap();
assert_eq!(&[BTreeSet::from([1, 2]), BTreeSet::from([3, 4])], rule.quorums());

let accepts = rule.is_quorum([4, 3, 9].iter());
assert!(accepts);
let accepts = rule.is_quorum([1, 3].iter());
assert!(!accepts);

// {3,4} misses {1,2}.
let intersects = rule.intersects_with(&rule);
assert_eq!(Some(false), intersects);

Implementations

impl<ID> ExplicitQuorumSet<ID>

where ID: Ord + Clone,

pub fn new<I>(quorums: I) -> Option<Self>

where I: IntoIterator<Item = BTreeSet<ID>>,

Builds a rule that accepts an ID set holding every ID of one of quorums.

Returns None when a listed quorum is empty: every set holds the empty set, so every set, the empty one included, would be a quorum.

pub fn quorums(&self) -> &[BTreeSet<ID>]

Returns the minimal quorums, sorted.

pub fn disjoint_quorums<'a>( &'a self, other: &'a Self, ) -> Option<(&'a BTreeSet<ID>, &'a BTreeSet<ID>)>

Returns the first pair of a listed quorum of self and a listed quorum of other that share no ID, in the order of the two lists, or None when every pair meets.

Such a pair shows two disjoint quorums, so None means the two rules have quorum intersection.

Trait Implementations

impl<ID: Clone> Clone for ExplicitQuorumSet<ID>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<ID: Debug> Debug for ExplicitQuorumSet<ID>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<ID: Eq> Eq for ExplicitQuorumSet<ID>

impl<ID: PartialEq> PartialEq for ExplicitQuorumSet<ID>

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

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.

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

Return Some(false) when a listed quorum of self and one of other are disjoint, and Some(true) otherwise. This check never returns None.

A rule with no listed quorum has no quorum, so it has quorum intersection with every rule.

impl<ID> QuorumSet for ExplicitQuorumSet<ID>

where ID: Ord + Clone,

type Id = ID

Node ID type in this quorum set.

type Iter = IntoIter<ID>

Iterator over every voter ID tracked by this quorum set.

fn is_quorum<'a, I>(&self, ids: I) -> bool

where ID: 'a, I: Iterator<Item = &'a ID> + Clone,

Return true if the candidate IDs satisfy this quorum rule.

fn ids(&self) -> Self::Iter

Return all voter IDs in this quorum set.

impl<ID: PartialEq> StructuralPartialEq for ExplicitQuorumSet<ID>