don't cast votes once there's a majority

2 files changed, 48 insertions, 4 deletions

diff --git a/src/remake/local.rs b/src/remake/local.rs
index a9a88b4..fd7c567 100644
--- a/src/remake/local.rs
+++ b/src/remake/local.rs
@@ -58,6 +58,8 @@ struct Inner {
     content_fetches: HashSet<[u8; 32]>,
     /// Remakes this node coordinates now (`coordinator`).
     coordinating: HashSet<String>,
+    /// The remake this node is about to vote for, and when (`vote_due`).
+    vote_due: Option<(String, UnixMillis)>,
     /// The actors this node writes or wrote with in the current document: this run's,
     /// and those of earlier runs it knows of (`--document-file`). Its own writes, for a
     /// rejoin. A switch or rejoin starts the list over with the new document's actor, so
@@ -186,6 +188,25 @@ impl RemakeState {
         self.lock().coordinating.contains(id)
     }
 
+    /// When this node votes for `remake` (`vote::cast`): asked first, `now` plus
+    /// `delay()`; asked again, the same time.
+    pub(crate) fn vote_due(
+        &self,
+        remake: &str,
+        now: UnixMillis,
+        delay: impl FnOnce() -> Duration,
+    ) -> UnixMillis {
+        let mut inner = self.lock();
+        match &inner.vote_due {
+            Some((id, due)) if id == remake => *due,
+            _ => {
+                let due = now.plus(delay());
+                inner.vote_due = Some((remake.to_owned(), due));
+                due
+            }
+        }
+    }
+
     fn lock(&self) -> MutexGuard<'_, Inner> {
         self.inner.lock_or_recover()
     }
diff --git a/src/remake/vote.rs b/src/remake/vote.rs
index cc805e3..669cab8 100644
--- a/src/remake/vote.rs
+++ b/src/remake/vote.rs
@@ -16,6 +16,10 @@
 //! and only once it holds the remake's content (`content`), so a committed remake has
 //! its content on a majority.
 //!
+//! Every vote is a change that reaches every node, and only a majority is needed. So a
+//! node waits a random part of half a keepalive interval before voting, and doesn't
+//! vote once the remake has its majority: of a large electorate, about half votes.
+//!
 //! A vote can be lost: a node whose vote reached only the coordinator restarts and
 //! resyncs from nodes that never saw it. Should it vote again for a competitor, its
 //! entry ends up with two concurrent values, and it counts for no remake. To avoid
@@ -23,6 +27,7 @@
 //! for is older than its start, and with one, votes only for that one.
 
 use std::collections::HashSet;
+use std::time::Duration;
 
 use tracing::{info, warn};
 
@@ -242,10 +247,12 @@ pub(super) async fn cast<H: Host>(host: &H) {
             let all = records::load_all(doc);
             let register = records::load_register(doc);
             let id = choice(&voter, &wanted, &all, &register, started, now, grace)?;
-            let content = all
-                .into_iter()
-                .find(|(other, _)| *other == id)
-                .and_then(|(_, record)| record.proposal.content);
+            let (_, record) = all.iter().find(|(other, _)| *other == id)?;
+            // Enough voted already: ours would only be one more change for everyone.
+            if tally(&id, record, &all, &register).reached() {
+                return None;
+            }
+            let content = record.proposal.content.clone();
             Some((id, content))
         })
         .await;
@@ -258,6 +265,12 @@ pub(super) async fn cast<H: Host>(host: &H) {
             return;
         }
     }
+    // Spread over half a keepalive interval, so later voters see the earlier votes
+    // (the worker checks every second).
+    let spread = host.dormant_after() / 8;
+    if now < host.remake().vote_due(&chosen, now, || random_part(spread)) {
+        return;
+    }
 
     // Decided again under the write lock, so two passes can't both vote.
     let voter = me.clone();
@@ -287,6 +300,16 @@ pub(super) async fn cast<H: Host>(host: &H) {
     }
 }
 
+/// A random duration below `limit`.
+fn random_part(limit: Duration) -> Duration {
+    let mut bytes = [0u8; 8];
+    if getrandom::fill(&mut bytes).is_err() {
+        return Duration::ZERO;
+    }
+    let limit_ms = limit.as_millis().max(1) as u64;
+    Duration::from_millis(u64::from_le_bytes(bytes) % limit_ms)
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;