aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/federation/model.rs36
-rw-r--r--src/federation/properties.rs60
2 files changed, 82 insertions, 14 deletions
diff --git a/src/federation/model.rs b/src/federation/model.rs
index 404bdb4..2107d9f 100644
--- a/src/federation/model.rs
+++ b/src/federation/model.rs
@@ -1,7 +1,7 @@
//! The model (`docs/federation-tests.md`, The harness): the federation read as
//! `docs/federation.md` says, as plainly as it can be. It reads every history anew from
-//! the root, keeps nothing between events but which it took, and makes no checkpoint.
-//! It is slow and short, and the fold is checked against it.
+//! the root, keeps nothing between events but which it took and whether it stopped, and
+//! makes no checkpoint. It is slow and short, and the fold is checked against it.
use std::collections::{BTreeMap, BTreeSet};
@@ -19,6 +19,9 @@ pub(crate) enum Verdict {
/// Some of its dependencies aren't taken yet.
Waiting,
Refused,
+ /// Neither taken nor refused: it stopped at a version it doesn't read, this event or
+ /// one before.
+ Stopped,
}
pub(crate) struct Model {
@@ -29,6 +32,8 @@ pub(crate) struct Model {
refused: BTreeSet<Id>,
/// Events offered whose dependencies aren't all taken yet.
waiting: Vec<Vec<u8>>,
+ /// Whether it stopped (`Changing the federation`): it takes and refuses nothing more.
+ stopped: bool,
}
impl Model {
@@ -42,6 +47,7 @@ impl Model {
taken: BTreeMap::new(),
refused: BTreeSet::new(),
waiting: Vec::new(),
+ stopped: false,
}
}
@@ -81,6 +87,9 @@ impl Model {
self.refused.insert(id);
return Verdict::Refused;
};
+ if self.stopped {
+ return Verdict::Stopped;
+ }
let deps = event.deps();
if deps.iter().any(|dep| self.refused.contains(dep)) {
self.refused.insert(id);
@@ -93,7 +102,15 @@ impl Model {
return Verdict::Waiting;
}
let history = self.history(deps);
- if self.judge(&history, &event, deps) && self.keeps(&event) {
+ if !self.judge(&history, &event, deps) {
+ self.refused.insert(id);
+ return Verdict::Refused;
+ }
+ if self.stops(&history, &event) {
+ self.stopped = true;
+ return Verdict::Stopped;
+ }
+ if self.keeps(&event) {
self.taken.insert(id, event);
Verdict::Taken
} else {
@@ -337,8 +354,9 @@ impl Model {
if 3 * yes.len() < 2 * current.parties.len() {
return false;
}
+ // None here: whether it is a version, a later continuum may say.
let Some(next) = self.written(version) else {
- return false;
+ return true;
};
if next.changes_validly(Some(&current)).is_err() {
return false;
@@ -402,6 +420,16 @@ impl Model {
.all(|dep| heads.contains(dep) || self.is_above(dep, heads))
}
+ /// Whether the node stops at `event`, at a history it judged: a version event whose
+ /// proposal is none here, changing the version the node reads, the one current there.
+ fn stops(&self, history: &BTreeSet<Id>, event: &Event) -> bool {
+ let Event::Version { version, .. } = event else {
+ return false;
+ };
+ let reads = |history: &BTreeSet<Id>| self.current(history).map(|current| current.hash);
+ self.written(version).is_none() && reads(history) == reads(&self.taken())
+ }
+
/// A node's own: a version event it takes only where its version changes the version
/// it reads, or is one it took.
fn keeps(&self, event: &Event) -> bool {
diff --git a/src/federation/properties.rs b/src/federation/properties.rs
index d42509b..02c7799 100644
--- a/src/federation/properties.rs
+++ b/src/federation/properties.rs
@@ -15,6 +15,7 @@ use super::event::{Checkpoint, Does, Event};
use super::fold::Federation;
use super::harness::{self, Party, Spec};
use super::held::Holding;
+use super::jcs::Json;
use super::model::{Model, Verdict};
use super::store::memory::{Offered, Refusal, Store};
use super::store::{Fold, Id};
@@ -82,12 +83,14 @@ impl History {
}
}
-/// How a history is written: whether an adversary takes part, and whether versions name
-/// checkpoints.
+/// How a history is written: whether an adversary takes part, whether versions name
+/// checkpoints, and whether parties propose versions this continuum doesn't read, at
+/// which a store stops, which events then take in the order they come.
#[derive(Clone, Copy)]
struct Kind {
adversary: bool,
checkpoints: bool,
+ unread: bool,
}
/// One of `ids`, of the latest five more often than not.
@@ -169,10 +172,27 @@ fn generate(rng: &mut Rng, kind: Kind) -> History {
next.rules
.push((format!("names/x{step}"), harness::str(&party.name)));
}
- let bytes = party.propose(&deps, &next.json());
- proposals.push((Id::of(&bytes), next.hash(), current.hash, named));
- specs.insert(next.hash(), next);
- bytes
+ if kind.unread && rng.chance(0.5) {
+ // A field this continuum doesn't know: none here.
+ let Json::Object(mut members) = next.json() else {
+ unreachable!("a version is an object")
+ };
+ members.push(("later".to_owned(), Json::Bool(true)));
+ let later = Json::object(members).expect("names once each");
+ let bytes = party.propose(&deps, &later);
+ proposals.push((
+ Id::of(&bytes),
+ Id::of(&later.bytes()),
+ current.hash,
+ named,
+ ));
+ bytes
+ } else {
+ let bytes = party.propose(&deps, &next.json());
+ proposals.push((Id::of(&bytes), next.hash(), current.hash, named));
+ specs.insert(next.hash(), next);
+ bytes
+ }
}
}
} else if roll < 85 {
@@ -297,19 +317,28 @@ fn verdict(offered: &Offered) -> Verdict {
Offered::Held => Verdict::Held,
Offered::Waiting => Verdict::Waiting,
Offered::Refused(_) => Verdict::Refused,
- // The harness proposes only versions this continuum reads: none stops the store.
- Offered::Stopped => unreachable!("the store stopped"),
+ Offered::Stopped => Verdict::Stopped,
}
}
+/// Where parties propose versions this continuum doesn't read too, the store stops where
+/// the model does: written in order, events come after what they build on, and both stop
+/// at the same event, taking the same before it.
#[test]
fn the_store_judges_and_reads_as_the_model() {
- for adversary in [false, true] {
+ let stopped = std::cell::Cell::new(0);
+ for (adversary, unread, cases) in [
+ (false, false, 48),
+ (true, false, 48),
+ (false, true, 32),
+ (true, true, 32),
+ ] {
check(
- 48,
+ cases,
Kind {
adversary,
checkpoints: false,
+ unread,
},
|history| {
let mut model = Model::new(&history.root);
@@ -325,6 +354,9 @@ fn the_store_judges_and_reads_as_the_model() {
));
}
}
+ if store.stopped().is_some() {
+ stopped.set(stopped.get() + 1);
+ }
if reads(&store) != model_reads(&model) {
return Err(format!(
"the store reads {:?}, the model {:?}",
@@ -336,6 +368,7 @@ fn the_store_judges_and_reads_as_the_model() {
},
);
}
+ assert!(stopped.get() > 0, "no history stopped a store");
}
#[test]
@@ -345,6 +378,7 @@ fn what_builds_on_a_refused_event_is_refused() {
Kind {
adversary: true,
checkpoints: true,
+ unread: false,
},
|history| {
let (store, _) = history.store(&history.written());
@@ -369,6 +403,7 @@ fn honest_parties_read_the_same_whatever_order_events_come_in() {
Kind {
adversary: false,
checkpoints: true,
+ unread: false,
},
|history| {
let held = holds(&history.store(&history.written()).0);
@@ -401,6 +436,7 @@ fn a_store_read_from_its_document_holds_what_one_given_the_events_alone_holds()
Kind {
adversary: false,
checkpoints: true,
+ unread: false,
},
|history| {
let alone = holds(&history.store(&history.written()).0);
@@ -456,6 +492,7 @@ fn after_a_checkpoint_the_store_judges_and_reads_as_the_whole_history() {
Kind {
adversary: false,
checkpoints: true,
+ unread: false,
},
|history| {
let (store, _) = history.store(&history.written());
@@ -533,6 +570,7 @@ fn every_version_a_store_takes_was_passed_by_two_thirds_in_its_history() {
Kind {
adversary: true,
checkpoints: false,
+ unread: false,
},
|history| {
let (store, _) = history.store(&history.written());
@@ -610,6 +648,7 @@ fn without_a_party_voting_twice_no_two_versions_change_one() {
Kind {
adversary: false,
checkpoints: true,
+ unread: false,
},
|history| {
let (store, _) = history.store(&history.written());
@@ -632,6 +671,7 @@ fn a_fork_keeps_what_counts_at_its_heads_and_takes_nothing_of_the_other() {
Kind {
adversary: false,
checkpoints: false,
+ unread: false,
},
|history| {
let (mut whole, _) = history.store(&history.written());