diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/config/mod.rs | 2 | ||||
| -rw-r--r-- | src/federation/vote.rs | 99 |
2 files changed, 89 insertions, 12 deletions
diff --git a/src/config/mod.rs b/src/config/mod.rs index 412753e..feb16e3 100644 --- a/src/config/mod.rs +++ b/src/config/mod.rs @@ -294,7 +294,7 @@ pub(crate) const OPTIONS: &[OptionSpec] = &[ Kind::Integer, "COUNT", None, - "With store-vote-key: propose a version that only moves to a checkpoint once it holds this many events beyond its checkpoint, at the heads of what it held for a while (store-held-for), where nothing that can still pass is proposed on the current version; it backs what it proposes.", + "With store-vote-key: propose a version that only moves to a checkpoint once it holds this many events beyond its checkpoint, at the heads of what it held for a while (store-held-for), where no proposal on the current version holds it back (docs/federation.md, Votes a node casts by itself); it backs what it proposes.", ), #[cfg(feature = "federation")] option( 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(¤t)) - && holds_back(¤t, other) + && holds_back(¤t, 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. |
