Struct QuorumTree 

pub struct QuorumTree<ID>
where
    ID: Ord,
{ /* private fields */ }

A single quorum rule represented as a tree.

QuorumTree models one side of a quorum configuration. A consensus implementation should usually build one tree for read quorums and another tree for write quorums, then ensure every read quorum intersects every write quorum.

A child node is selected when it is either an included node ID or a nested quorum tree whose own quorum rule is satisfied.

Invariants

• A QuorumTree represents exactly one quorum rule.
• Child nodes are unique and traversal order is deterministic according to Node ordering.
• quorum_size never exceeds the number of child nodes: construction rejects duplicate children and unsatisfiable quorum sizes.
• Equality and ordering for QuorumTree are based only on its canonical ID.
• Canonical IDs are stable identifiers. std::fmt::Display is human-readable output and is not a serialization format.

Implementations

impl<ID> QuorumTree<ID>

where ID: Ord,

pub fn new( quorum_size: u64, nodes: impl IntoIterator<Item = Node<ID>>, ) -> Result<Self, QuorumTreeError>

where ID: CanonicalId,

Builds a quorum tree from a quorum size and child nodes.

quorum_size is the number of child nodes that must be selected for this tree to be selected. A child can be a single ID or another quorum tree. If quorum_size is 0, every input satisfies the tree.

Errors

• QuorumTreeError::DuplicateChild: a child was given more than once. A duplicate child is always an upstream bug; a tree never contains the same child twice.
• QuorumTreeError::UnsatisfiableQuorum: quorum_size exceeds the number of child nodes, so no input could satisfy the tree.

Examples

use quorum_set::{Node, QuorumSet, QuorumTree, QuorumTreeError};

let tree = QuorumTree::new(2, [
    Node::Id(1),
    Node::Id(2),
    Node::Id(3),
]).unwrap();

assert!(tree.is_quorum([1, 2].iter()));
assert!(!tree.is_quorum([1].iter()));

let err = QuorumTree::new(1, [Node::Id(1), Node::Id(1)]).unwrap_err();
assert_eq!(
    QuorumTreeError::DuplicateChild { canonical_id: "Id=1".to_string() },
    err
);

pub fn quorum_size(&self) -> u64

Returns the number of selected child nodes required to satisfy this tree.

pub fn children(&self) -> impl Iterator<Item = &Node<ID>>

Returns this tree’s child nodes in canonical order.

Children are unique: construction rejects duplicate child nodes.

pub fn canonical_id(&self) -> &str

Returns the canonical ID of this tree.

The canonical ID decides equality and ordering. It is computed once at construction, so this accessor does not allocate.

Trait Implementations

impl<ID> CanonicalId for QuorumTree<ID>

where ID: Ord + CanonicalId,

fn fmt_canonical_id<W>(&self, f: &mut W) -> Result

where W: Write + ?Sized,

Writes this value’s canonical ID into f.

fn canonical_id(&self) -> String

Returns this value’s canonical ID as a String.

impl<ID> Clone for QuorumTree<ID>

where ID: Ord + Clone,

fn clone(&self) -> QuorumTree<ID>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<ID> Debug for QuorumTree<ID>

where ID: Ord + Debug,

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

Formats the value using the given formatter.

impl<ID> Display for QuorumTree<ID>

where ID: Ord + Display,

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

Formats the value using the given formatter.

impl<ID> Eq for QuorumTree<ID>

where ID: Ord,

impl<ID> Hash for QuorumTree<ID>

where ID: Ord,

Hashing is based solely on canonical_id, consistent with equality.

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<ID> Ord for QuorumTree<ID>

where ID: Ord,

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<ID> PartialEq for QuorumTree<ID>

where ID: Ord,

Equality and ordering are decided solely by canonical_id.

new() is the sole constructor and canonical_id is the cached canonical representation of the quorum tree spec. A single string comparison keeps BTreeSet operations cheap; no recursive structural comparison is needed.

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<ID> PartialOrd for QuorumTree<ID>

where ID: Ord,

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<ID> QuorumSet for QuorumTree<ID>

where ID: Ord + Clone + 'static,

Hierarchical quorum implementation for QuorumTree.

Evaluation follows the tree structure. ids() returns all leaf IDs once, even when the same node appears in more than one subtree.

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: Iterator<Item = &'a ID> + Clone>(&self, ids: I) -> bool

Return true if the candidate IDs satisfy this quorum rule.

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

Return all voter IDs in this quorum set.