aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation')
-rw-r--r--src/federation/vote.rs99
1 files changed, 88 insertions, 11 deletions
diff --git a/src/federation/vote.rs b/src/federation/vote.rs
index bf866e7..4c4cdfa 100644
--- a/src/federation/vote.rs
+++ b/src/federation/vote.rs
@@ -5,13 +5,14 @@
//! * **Following**: it votes `true` on a proposal on the current version where a party it
//! follows voted `true`, never `false`; by default only on a version that only moves to a
//! checkpoint (`Version::only_moves_on`), and then only where no proposal that changes
-//! more can still pass, but one nobody backs but its proposer (`holds_back`), as such a
-//! version lapses it.
+//! more holds it back (`holds_back`), as such a version lapses it.
//! * **Proposing a checkpoint**: once so many events are held beyond its checkpoint, or so
//! long after it moved there by its own clock, it proposes a version that only moves to
-//! a checkpoint, at the heads of what it held for a while, where nothing that can still
-//! pass is proposed on the current version, but a proposal it wouldn't back that nobody
-//! backs but its proposer. It backs what it proposes.
+//! a checkpoint, at the heads of what it held for a while, where no proposal on the
+//! current version holds it back: one it would back that can still pass, one that can
+//! still pass that a third of the parties back, someone but its proposer among them, or
+//! one new, held less than a while, whose proposer has no older one on the version
+//! (`holds_back`). It backs what it proposes.
//! * **Voting `false` beside**: where it backs a proposal that can still pass, it votes
//! `false` on every other proposal on the current version that only moves to a
//! checkpoint, so that, of two checkpoints proposed at once, the one it doesn't back
@@ -208,10 +209,21 @@ fn alive(current: &Version, proposed: &Proposed) -> bool {
3 * (parties - proposed.no.len().min(parties)) >= 2 * parties
}
-/// Whether `proposed` holds back a version that only moves to a checkpoint, which would
-/// lapse it: it can still pass, and someone but its proposer backs it.
-fn holds_back(current: &Version, proposed: &Proposed) -> bool {
- alive(current, proposed) && !proposed.yes.is_subset(&proposed.proposers)
+/// Whether `proposed`, of `all`, holds back a version that only moves to a checkpoint,
+/// which would lapse it: it can still pass, and a third of the parties back it, someone
+/// but its proposer among them; or it came less than `grace` ago, and its proposer has no
+/// older proposal on the version. So two parties keep no proposal alive to hold back
+/// checkpoints, and one new is lapsed by none before its proposer is heard, once.
+fn holds_back(current: &Version, proposed: &Proposed, all: &[Proposed], grace: Duration) -> bool {
+ let backed = !proposed.yes.is_subset(&proposed.proposers)
+ && 3 * proposed.yes.len() >= current.parties.len();
+ let fresh = proposed.held < grace
+ && !all.iter().any(|other| {
+ other.hash != proposed.hash
+ && other.held >= grace
+ && !other.proposers.is_disjoint(&proposed.proposers)
+ });
+ alive(current, proposed) && (backed || fresh)
}
/// What a node voting by itself by `rules` signs now, as it sees its store, by
@@ -262,7 +274,7 @@ pub(crate) fn decide(seen: &Seen<'_>, rules: &Rules, record: &Record) -> Vec<Act
.version
.as_ref()
.is_some_and(|version| version.only_moves_on(&current))
- && holds_back(&current, other)
+ && holds_back(&current, other, &all, rules.held_for)
});
if !own_one && moves_on && lapses {
continue;
@@ -409,7 +421,7 @@ fn checkpoint(seen: &Seen<'_>, rules: &Rules, current: &Version, all: &[Proposed
version.only_moves_on(current)
&& backs_checkpoint(seen, rules, current, version, proposed.held).is_ok()
});
- (alive(current, proposed) && backs) || holds_back(current, proposed)
+ (alive(current, proposed) && backs) || holds_back(current, proposed, all, rules.held_for)
});
if blocked {
return None;
@@ -642,6 +654,71 @@ mod tests {
assert!(decide(&seen(&store, &long), &rules, &record).is_empty());
}
+ /// Of nine parties, two keep a proposal alive: it holds back no checkpoint a node
+ /// proposes, as fewer than a third back it. A new one holds back for a while, but not
+ /// one from a proposer whose earlier one is past that while.
+ #[test]
+ fn two_parties_hold_back_no_checkpoint_but_a_new_proposal_does_for_a_while() {
+ let parties: Vec<Party> = (1..=9).map(|n| Party::new(&format!("p{n}"), n)).collect();
+ let named: Vec<&Party> = parties.iter().collect();
+ let first = Spec::first(&named, &[]);
+ let mut store = Store::new(first.root(), Vec::new()).expect("a root");
+ let root = store.id();
+ let on = first.hash();
+ let write = taken(
+ &mut store,
+ parties[2].write(&[root], "home/p3/a", harness::str("1")),
+ );
+ let junk = |n: usize| {
+ let mut junk = first.after(on);
+ junk.rules.push((format!("names/x{n}"), harness::str("p1")));
+ junk
+ };
+ let old = taken(&mut store, parties[0].propose(&[root], &junk(1).json()));
+ taken(
+ &mut store,
+ parties[0].vote(&[old], on, junk(1).hash(), true),
+ );
+ taken(
+ &mut store,
+ parties[1].vote(&[old], on, junk(1).hash(), true),
+ );
+ let rules = Rules {
+ propose_events: Some(1),
+ held_for: Duration::from_secs(60),
+ ..Rules::default()
+ };
+ let record = record(&store, "p3");
+ let proposes = |acts: Vec<Act>| matches!(acts.as_slice(), [Act::Propose(_)]);
+ let long = |_: &Id| Some(Duration::from_secs(3600));
+ assert!(proposes(decide(&seen(&store, &long), &rules, &record)));
+ // One by p4, new: held back, for a while.
+ let new = taken(&mut store, parties[3].propose(&[write], &junk(2).json()));
+ let fresh = |id: &Id| {
+ Some(if *id == new {
+ Duration::from_secs(1)
+ } else {
+ Duration::from_secs(3600)
+ })
+ };
+ assert!(decide(&seen(&store, &fresh), &rules, &record).is_empty());
+ assert!(proposes(decide(&seen(&store, &long), &rules, &record)));
+ // One by p1 again, new, while its old one is past that while: not.
+ let again = taken(&mut store, parties[0].propose(&[write], &junk(3).json()));
+ let fresh_again = |id: &Id| {
+ Some(if *id == again {
+ Duration::from_secs(1)
+ } else {
+ Duration::from_secs(3600)
+ })
+ };
+ assert!(proposes(decide(
+ &seen(&store, &fresh_again),
+ &rules,
+ &record
+ )));
+ }
+
/// A node backs no checkpoint, and proposes none, before its store held its checkpoint,
/// or ran, for a while: a party it follows moves the store once that long at most, and
/// just started it holds nothing for a while yet.