quorum_set/quorum/
quorum_set.rs

1use std::sync::Arc;
2
3#[cfg(doc)]
4use crate::BothQuorums;
5#[cfg(doc)]
6use crate::QuorumTree;
7#[cfg(doc)]
8use crate::VecProgress;
9#[cfg(doc)]
10use crate::verify_intersection;
11
12/// Common interface for every quorum rule supported by this crate.
13///
14/// A quorum is a collection of nodes that a read or write operation in a distributed system has to
15/// contact. See: <http://web.mit.edu/6.033/2005/wwwdocs/quorum_note.html>
16///
17/// Every implementation must follow three rules:
18///
19/// - Upward-closed: adding IDs to an accepted quorum keeps it accepted. [`VecProgress`] and
20///   [`verify_intersection`] rely on this rule.
21/// - Closed over [`ids()`](Self::ids): an ID that `ids()` does not yield never changes the result
22///   of [`is_quorum()`](Self::is_quorum). [`verify_intersection`] enumerates only the IDs that
23///   `ids()` yields, so it relies on this rule.
24/// - Duplicate-safe: an ID that appears more than once in the `is_quorum()` input counts once, so
25///   callers may pass an iterator with repeats.
26///
27/// The crate provides implementations for flat majority sets, joint quorum sets, hierarchical
28/// [`QuorumTree`] rules, and [`BothQuorums`], which requires both a read and a write quorum.
29pub trait QuorumSet {
30    /// Node ID type in this quorum set.
31    type Id;
32
33    /// Iterator over every voter ID tracked by this quorum set.
34    ///
35    /// Implementations that combine multiple sub-rules return each ID once.
36    type Iter: Iterator<Item = Self::Id>;
37
38    /// Return `true` if the candidate IDs satisfy this quorum rule.
39    ///
40    /// Repeated IDs count once, and IDs that [`ids()`](Self::ids) does not yield are ignored.
41    fn is_quorum<'a, I>(&self, ids: I) -> bool
42    where
43        Self::Id: 'a,
44        I: Iterator<Item = &'a Self::Id> + Clone;
45
46    /// Return all voter IDs in this quorum set.
47    fn ids(&self) -> Self::Iter;
48}
49
50impl<T> QuorumSet for Arc<T>
51where T: QuorumSet
52{
53    type Id = T::Id;
54
55    type Iter = T::Iter;
56
57    fn is_quorum<'a, I>(&self, ids: I) -> bool
58    where
59        Self::Id: 'a,
60        I: Iterator<Item = &'a Self::Id> + Clone,
61    {
62        self.as_ref().is_quorum(ids)
63    }
64
65    fn ids(&self) -> Self::Iter {
66        self.as_ref().ids()
67    }
68}
quorum_set/quorum/quorum_set.rs

quorum_set/quorum/
quorum_set.rs
