From b00371d1260f4379241a9226d576270dd3a68285 Mon Sep 17 00:00:00 2001 From: tv Date: Thu, 19 Nov 2026 01:48:58 +0000 Subject: vote: a proposal holds back checkpoints by a third, or new for a while A node voting by itself proposes no checkpoint beside a proposal that holds it back, as the checkpoint would lapse it, and a follower backs none so. A proposal held one back where someone but its proposer backed it: two parties, or one and a stolen key, kept a junk proposal alive, and no automatic checkpoint came while it lived, ending it taking nays from more than a third each round. And one new, its proposer alone backing it, was lapsed at once by a checkpoint its writes brought about. A proposal that can still pass holds back now where a third of the parties back it, someone but its proposer among them; or where it is new, held for less than a while (`--store-held-for`), and its proposer has none older on the version: so it is heard before a checkpoint lapses it, once a version for each proposer. Row 67 says so, and a test of nine parties checks it. --- src/federation/vote.rs | 99 ++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 88 insertions(+), 11 deletions(-) (limited to 'src/federation') 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, 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 = (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| 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. -- cgit v1.3.1