Struct HierarchicalQuorumSet 

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

A quorum rule over a tree of groups: it accepts an ID set that reaches the root group.

A Group holds IDs, child groups, or both: its members. A set reaches a group when the IDs of the group that it holds, plus the child groups that it reaches, number at least the quorum size of the group.

Each group has a name that is stable among its siblings, such as the name of a zone, and each ID belongs to exactly one group. new() checks that every group of the tree holds a member and has 1 <= quorum_size <= member_count, and that no ID appears twice in the tree. So every group can be reached, and the set of all IDs is a quorum.

The intersection check proves Some(true) for two rules over the same tree when their quorum sizes sum to more than the member count of every group, as a rule and its dual() do. It answers None for every other pair.

Examples

use std::collections::BTreeMap;
use std::collections::BTreeSet;

use quorum_set::{Group, HierarchicalQuorumSet, QuorumIntersection, QuorumSet};

// Zone a has racks r1 = {1, 2} and r2 = {3, 4}, zone b holds IDs 5 and 6, and ID 7
// sits at the root. A quorum reaches 2 of zone a, zone b and ID 7. It reaches zone a
// through an ID in each rack, and zone b through both of its IDs.
let a = Group::of_groups(2, [
    ("r1", Group::of_ids(1, [1, 2])),
    ("r2", Group::of_ids(1, [3, 4])),
]);
let b = Group::of_ids(2, [5, 6]);
let root = Group {
    quorum_size: 2,
    ids: BTreeSet::from([7]),
    groups: BTreeMap::from([("a".to_string(), a), ("b".to_string(), b)]),
};
let rule = HierarchicalQuorumSet::new(root).unwrap();

let accepts = rule.is_quorum([1, 3, 7].iter());
assert!(accepts);
// Rack r2 is lost, so only zone b is reached.
let accepts = rule.is_quorum([1, 2, 5, 6].iter());
assert!(!accepts);

// The quorums {1, 3, 7} and {2, 4, 5, 6} both reach zone a, through other IDs of each
// rack. The check proves nothing, because the two quorum sizes of a rack sum to only its
// member count.
let intersects = rule.intersects_with(&rule);
assert_eq!(None, intersects);

Implementations

impl<ID> HierarchicalQuorumSet<ID>

where ID: Ord + Clone,

pub fn new(root: Group<ID>) -> Result<Self, HierarchicalQuorumSetError<ID>>

Builds a rule that accepts an ID set reaching root.

Returns HierarchicalQuorumSetError for the first problem in a walk of the tree that visits a group before the groups below it, and sibling groups in name order: a group that holds no member, a group without 1 <= quorum_size <= member_count, or an ID that a visited group already holds.

pub fn root(&self) -> &Group<ID>

Returns the root group, which holds every ID of the rule in its tree.

pub fn dual(&self) -> Self

Returns the rule over the same tree that accepts exactly the sets that meet every quorum of self.

A quorum of self that misses a set S takes its IDs from outside S. Because no ID appears twice in the tree, it can reach the members of a group independently: each ID outside S, and each child group that S does not block. S blocks a group when it leaves fewer than quorum_size members reachable, so when it holds or blocks member_count - quorum_size + 1 members: the IDs that it holds and the child groups that it blocks. S meets every quorum exactly when it blocks the root group. So the result keeps the tree and gives every group that number as its quorum size.

Trait Implementations

impl<ID: Clone> Clone for HierarchicalQuorumSet<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 HierarchicalQuorumSet<ID>

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

Formats the value using the given formatter.

impl<ID: Eq> Eq for HierarchicalQuorumSet<ID>

impl<ID: PartialEq> PartialEq for HierarchicalQuorumSet<ID>

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

Equality operator ==.

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

Inequality operator !=.

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).

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

Return Some(true) when both rules hold the same IDs and the same child group names in every group, and the two quorum sizes of every group sum to more than its member count.

Return None otherwise, including for rules over different trees, such as after an ID moves to another group: the check proves nothing for them. This check never returns Some(false).

impl<ID> QuorumSet for HierarchicalQuorumSet<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 HierarchicalQuorumSet<ID>