--- a/Cargo.toml
+++ b/Cargo.toml
@@ -185,7 +185,7 @@ version = "0.2.16"
 version = "0.5.1"
 
 [dependencies.rand]
-version = "0.9.1"
+version = "0.8"
 
 [dependencies.regex]
 version = "1.12.2"
--- a/src/runner/executor.rs
+++ b/src/runner/executor.rs
@@ -39,7 +39,7 @@ use crate::{
 use future_queue::FutureQueueContext;
 use nextest_metadata::FilterMatch;
 use quick_junit::ReportUuid;
-use rand::{Rng, distr::OpenClosed01};
+use rand::{Rng, distributions::OpenClosed01};
 use std::{
     fmt,
     num::NonZeroUsize,
@@ -1134,7 +1134,7 @@ impl BackoffIter {
     }
 
     fn apply_jitter(duration: Duration) -> Duration {
-        let jitter: f64 = rand::rng().sample(OpenClosed01);
+        let jitter: f64 = rand::thread_rng().sample(OpenClosed01);
         // Apply jitter in the range (0.5, 1].
         duration.mul_f64(0.5 + jitter / 2.)
     }
--- a/src/record/tree.rs
+++ b/src/record/tree.rs
@@ -289,7 +289,6 @@ mod tests {
     use super::*;
     use chrono::TimeZone;
     use proptest::prelude::*;
-    use rand::seq::SliceRandom;
     use test_strategy::proptest;
 
     fn make_run(id_suffix: u32, parent_suffix: Option<u32>, hours_ago: i64) -> RunInfo {
@@ -1001,9 +1000,13 @@ mod tests {
 
     /// Strategy to generate a forest and a shuffled version of it.
     fn arb_forest_with_shuffle() -> impl Strategy<Value = (Vec<RunInfo>, Vec<RunInfo>)> {
-        arb_forest().prop_perturb(|original, mut rng| {
+        // proptest 1.11's TestRng implements rand 0.9, not the archive rand 0.8.
+        arb_forest().prop_map(|original| {
             let mut shuffled = original.clone();
-            shuffled.shuffle(&mut rng);
+            shuffled.reverse();
+            if shuffled.len() > 1 {
+                shuffled.rotate_left(1);
+            }
             (original, shuffled)
         })
     }
