aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--docs/federation.md27
-rw-r--r--docs/guides/federation/checkpoints.md9
-rw-r--r--docs/guides/federation/voting-by-itself.md12
-rw-r--r--src/config/mod.rs2
-rw-r--r--src/federation/vote.rs99
5 files changed, 117 insertions, 32 deletions
diff --git a/docs/federation.md b/docs/federation.md
index 784915a..1d77e4f 100644
--- a/docs/federation.md
+++ b/docs/federation.md
@@ -511,20 +511,23 @@ as it judges any vote or proposal. The design has two in mind:
and its `true` shown to some and its `false` to the rest would pass a proposal at one
history and make it dead at another. By default it follows only on a version that only
moves to a checkpoint ([Checkpoints](#checkpoints)), and only where no proposal that
- changes more can still pass, but one nobody backs but its proposer: such a version
- lapses every other proposal, and the party it follows would end any it disliked by
- passing one. Even so, the parties following one hand it their votes on checkpoints: with
- them, it passes one at heads of its choosing, by the voters' rule (below). Its operator
- may have it follow on any version, which hands that party the node's `true`: a party
- followed so by two thirds of the parties, its key kept on a node, passes what it backs.
+ changes more holds it back (below): such a version lapses every other proposal, and the
+ party it follows would end any it disliked by passing one. Even so, the parties
+ following one hand it their votes on checkpoints: with them, it passes one at heads of
+ its choosing, by the voters' rule (below). Its operator may have it follow on any
+ version, which hands that party the node's `true`: a party followed so by two thirds of
+ the parties, its key kept on a node, passes what it backs.
* **Proposing a checkpoint**: propose a version that only moves to a checkpoint, at
heads the node has held for a while, once conditions its operator sets are met: so
many events or bytes held beyond its checkpoint, so many versions since it, or so long
- by its own clock, by which nothing anyone judges goes. It proposes only where nothing
- that can still pass is proposed on the current version, as such a version lapses what
- is, but a proposal it wouldn't back that nobody backs but its proposer: so a party
- keeping one alive holds back no checkpoint. It backs what it proposes, so that the
- nodes following its party back it too.
+ by its own clock, by which nothing anyone judges goes. It proposes only where no
+ proposal on the current version holds it back, as such a version lapses what is: 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 for less than a while, whose
+ proposer has none older on the version. So neither a party keeping a proposal alive,
+ nor two of a federation of seven or more, hold back checkpoints, and a new proposal is
+ lapsed by none before its proposer is heard, once a version. It backs what it proposes,
+ so that the nodes following its party back it too.
Such a node keeps to what a party's client keeps to: one yes at a time; never `true` and
`false` on one proposal, so a party has one node vote by itself, as two of its nodes
@@ -738,7 +741,7 @@ fold, with crafted events. *Sim*: a simulation. *Bench*: measured, not judged.
| 64 | Checkpoint heads before the current checkpoint, or at which it isn't current, or one in another's history | No version: a version event naming it is refused | unit |
| 65 | After a checkpoint, a party that backed a second proposal once its first was dead, the nays that freed it withheld by those who cast them | Not named: its client keeps those nays with its `true` | unit |
| 66 | Two clients of one party back two proposals at once, or its operator votes by hand beside the node that votes for it | Voting twice: a party votes from one client, the node that votes for it where it has one, through which it votes by hand | — |
-| 67 | A party keeps a proposal alive that nobody else backs, to hold back automatic checkpoints | Holds back none: a node proposes a checkpoint beside a proposal it wouldn't back that nobody backs but its proposer | sim |
+| 67 | A party keeps a proposal alive that nobody else backs, or two parties of seven or more, to hold back automatic checkpoints | Holds back none past a while: a node proposes a checkpoint beside a proposal it wouldn't back that fewer than a third of the parties back, or nobody but its proposer; a new one holds back for a while, once a version for its proposer | sim |
| 68 | A checkpoint proposed at heads that leave out what was written since: a key set dropping a stolen key, say | Not backed: clients and nodes back a checkpoint only where what they held for a while is among its heads, in their history, or above them; a node shows what they lack | unit |
| 69 | A key a version names, stolen, writes its party's node list at a history from before the version naming the party's keys anew, beside the list the party writes under that version, several, for the lowest ID | The party's counts: of a party's lists, those written under the latest version come first | unit |
| 70 | A checkpoint's version proposed again, by an event beside its heads | Voters back it all the same, as a proposal lapses with the move, and vote on the events proposing it above its heads, as a node shows them; a version event on votes beside them is refused | unit |
diff --git a/docs/guides/federation/checkpoints.md b/docs/guides/federation/checkpoints.md
index 345bc98..f935421 100644
--- a/docs/guides/federation/checkpoints.md
+++ b/docs/guides/federation/checkpoints.md
@@ -37,8 +37,9 @@ nothing that can still pass is proposed on the current version.
A node voting for its party by itself proposes checkpoints by its operator's rules: once
it holds so many events beyond its checkpoint (`--store-propose-events`), or so long
after its store moved there (`--store-propose-every`), at the heads of what it held for
-a while (`--store-held-for`, ten minutes unless set), where nothing that can still pass
-is proposed; and it backs what it proposes.
+a while (`--store-held-for`, ten minutes unless set), where no proposal holds it back
+([`voting-by-itself.md`](voting-by-itself.md), [Its rules](voting-by-itself.md#its-rules));
+and it backs what it proposes.
## Backing one
@@ -52,7 +53,9 @@ yourself, or vote through such a node.
* `--store-follow PARTY,…` has a node voting by itself follow those parties' `true`,
by default on versions that only move to a checkpoint, and still by that rule, but not
- where a proposal changing more can still pass that someone but its proposer backs.
+ where a proposal changing more holds it back, as a node proposing one keeps to
+ ([`voting-by-itself.md`](voting-by-itself.md),
+ [Its rules](voting-by-itself.md#its-rules)).
* `--store-back-after` (ten minutes unless set) has it back none before its store held its
checkpoint, or ran, that long.
* `--store-nay-beside` has it vote `false` on every other version only moving to a
diff --git a/docs/guides/federation/voting-by-itself.md b/docs/guides/federation/voting-by-itself.md
index 97f4eff..cfcdcf3 100644
--- a/docs/guides/federation/voting-by-itself.md
+++ b/docs/guides/federation/voting-by-itself.md
@@ -38,8 +38,8 @@ or `POST /admin/events/vote` with `{"proposal": "8d02…", "yes": true}`.
* **Following** (`--store-follow PARTY,…`): it votes `true` on a proposal where a party
it follows voted `true`, never `false`; by default only on a version that only moves to
- a checkpoint, and only where no proposal changing more can still pass that someone but
- its proposer backs, as a checkpoint lapses it. Even so, the parties following one hand
+ a checkpoint, and only where no proposal changing more holds it back (below), as a
+ checkpoint lapses it. Even so, the parties following one hand
it their votes on checkpoints. With `--store-follow-any`, on any version: that hands
those parties the node's `true`. A party followed so by two thirds of the parties, with
its key kept on a node, passes what it backs.
@@ -51,9 +51,11 @@ or `POST /admin/events/vote` with `{"proposal": "8d02…", "yes": true}`.
DURATION`): once it holds so many events beyond its checkpoint, or so long after its
store 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 (`--store-held-for`, ten minutes
- unless set), 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, so that the nodes following its party back it too.
+ unless set), 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 held for less than a while whose proposer has none
+ older on the version. It backs what it proposes, so that the nodes following its party
+ back it too.
* **`false` beside** (`--store-nay-beside`): where it backs a proposal that can still
pass, it votes `false` on every other version only moving to a checkpoint, so that of
two checkpoints proposed at once the other dies, and its backers are free.
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(&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.