quorum_set/quorum/
coherent.rs

1use crate::quorum::QuorumSet;
2
3/// Relation between quorum sets whose quorums always intersect.
4///
5/// **Coherent** quorum set A and B is defined as:
6/// `∀ qᵢ ∈ A, ∀ qⱼ ∈ B: qᵢ ∩ qⱼ != ø`, i.e., `A ~ B`.
7/// In words, every quorum in A intersects every quorum in B. Consensus
8/// protocols use this relation to make membership changes without losing
9/// overlap between old and new decisions.
10///
11/// In a Raft-style membership change, coherence is one safety requirement. The
12/// protocol also has to prevent an old, smaller candidate from being elected
13/// during the transition.
14pub trait Coherent<ID, Other>
15where
16    ID: PartialOrd + Ord + 'static,
17    Self: QuorumSet<Id = ID>,
18    Other: QuorumSet<Id = ID>,
19{
20    /// Return `true` if this quorum set is coherent with the other quorum set.
21    fn is_coherent_with(&self, other: &Other) -> bool;
22}
23
24/// Finds an intermediate quorum set coherent with both source and target quorum sets.
25pub trait FindCoherent<ID, Other>
26where
27    ID: PartialOrd + Ord + 'static,
28    Self: QuorumSet<Id = ID>,
29    Other: QuorumSet<Id = ID>,
30{
31    /// Build a quorum set `X` so that `self` is coherent with `X` and `X` is
32    /// coherent with `other`, i.e., `self ~ X ~ other`.
33    ///
34    /// Then `X` is the intermediate quorum set when changing membership from
35    /// `self` to `other`.
36    ///
37    /// E.g.(`cᵢcⱼ` is a joint of `cᵢ` and `cⱼ`):
38    /// - `c₁.find_coherent(c₁)`   returns `c₁`
39    /// - `c₁.find_coherent(c₂)`   returns `c₁c₂`
40    /// - `c₁c₂.find_coherent(c₂)` returns `c₂`
41    /// - `c₁c₂.find_coherent(c₁)` returns `c₁`
42    /// - `c₁c2.find_coherent(c₃)` returns `c₂c₃`
43    fn find_coherent(&self, other: Other) -> Self;
44}
quorum_set/quorum/coherent.rs

quorum_set/quorum/
coherent.rs
