rusty_time_core/
select.rs

1//! Source selection: falseticker rejection by interval intersection (RFC 5905 §11.2.1)
2//! and weighted combining.
3
4/// One source's current estimate, as fed to selection.
5#[derive(Clone, Copy, Debug, PartialEq)]
6pub struct SourceEstimate {
7    /// Caller's identifier for the source (index, socket id, …).
8    pub id: usize,
9    /// Seconds to add to the local clock.
10    pub offset: f64,
11    /// Root distance: delay/2 + dispersion, seconds. Bounds the interval.
12    pub root_distance: f64,
13    pub stratum: u8,
14}
15
16#[derive(Clone, Debug, Default, PartialEq)]
17pub struct Selection {
18    /// ids of sources judged truechimers, best first.
19    pub truechimers: Vec<usize>,
20    /// Combined offset (weighted by 1/root_distance), if any source survived.
21    pub offset: Option<f64>,
22}
23
24/// Find the largest clique of sources whose correctness intervals
25/// `[offset - root_distance, offset + root_distance]` share a common point, then
26/// combine the survivors.
27pub fn select(sources: &[SourceEstimate]) -> Selection {
28    let n = sources.len();
29    if n == 0 {
30        return Selection::default();
31    }
32
33    // Endpoint sweep, per RFC 5905: find [low, high] contained in at least n - f
34    // intervals, for the smallest achievable number of falsetickers f.
35    #[derive(Clone, Copy)]
36    struct Edge {
37        value: f64,
38        kind: i32, // +1 = lower endpoint, -1 = upper endpoint
39    }
40    let mut edges: Vec<Edge> = Vec::with_capacity(2 * n);
41    for s in sources {
42        let rd = s.root_distance.max(1e-9);
43        edges.push(Edge {
44            value: s.offset - rd,
45            kind: 1,
46        });
47        edges.push(Edge {
48            value: s.offset + rd,
49            kind: -1,
50        });
51    }
52    edges.sort_by(|a, b| a.value.total_cmp(&b.value));
53
54    let mut chosen: Option<(f64, f64)> = None;
55    for f in 0..=(n.saturating_sub(1)) / 2 {
56        let need = (n - f) as i32;
57        // Scan up for the low endpoint.
58        let mut count = 0;
59        let mut low = None;
60        for e in &edges {
61            count += e.kind;
62            if count >= need {
63                low = Some(e.value);
64                break;
65            }
66        }
67        // Scan down for the high endpoint.
68        let mut count = 0;
69        let mut high = None;
70        for e in edges.iter().rev() {
71            count -= e.kind;
72            if count >= need {
73                high = Some(e.value);
74                break;
75            }
76        }
77        if let (Some(lo), Some(hi)) = (low, high)
78            && lo <= hi
79        {
80            chosen = Some((lo, hi));
81            break;
82        }
83    }
84
85    let Some((lo, hi)) = chosen else {
86        return Selection::default();
87    };
88
89    let mut survivors: Vec<&SourceEstimate> = sources
90        .iter()
91        .filter(|s| {
92            let rd = s.root_distance.max(1e-9);
93            s.offset + rd >= lo && s.offset - rd <= hi
94        })
95        .collect();
96    if survivors.is_empty() {
97        return Selection::default();
98    }
99
100    // Best first: lowest stratum, then tightest interval.
101    survivors.sort_by(|a, b| {
102        (a.stratum, a.root_distance)
103            .partial_cmp(&(b.stratum, b.root_distance))
104            .unwrap_or(core::cmp::Ordering::Equal)
105    });
106
107    let mut wsum = 0.0;
108    let mut osum = 0.0;
109    for s in &survivors {
110        let w = 1.0 / s.root_distance.max(1e-9);
111        wsum += w;
112        osum += w * s.offset;
113    }
114
115    Selection {
116        truechimers: survivors.iter().map(|s| s.id).collect(),
117        offset: (wsum > 0.0).then(|| osum / wsum),
118    }
119}
120
121#[cfg(test)]
122mod tests {
123    use super::*;
124
125    fn src(id: usize, offset: f64, rd: f64) -> SourceEstimate {
126        SourceEstimate {
127            id,
128            offset,
129            root_distance: rd,
130            stratum: 2,
131        }
132    }
133
134    #[test]
135    fn falseticker_is_excluded() {
136        let sources = [
137            src(0, 0.001, 0.005),
138            src(1, 0.002, 0.005),
139            src(2, 0.0015, 0.005),
140            src(3, 0.500, 0.005), // liar
141        ];
142        let sel = select(&sources);
143        assert_eq!(sel.truechimers.len(), 3);
144        assert!(!sel.truechimers.contains(&3));
145        let o = sel.offset.expect("offset");
146        assert!(o > 0.0005 && o < 0.0035, "combined {o}");
147    }
148
149    #[test]
150    fn all_disjoint_yields_majority_failure() {
151        let sources = [
152            src(0, 0.0, 0.001),
153            src(1, 1.0, 0.001),
154            src(2, 2.0, 0.001),
155            src(3, 3.0, 0.001),
156        ];
157        let sel = select(&sources);
158        // No majority clique exists; selection must not invent one.
159        assert!(sel.offset.is_none() || sel.truechimers.len() <= 2);
160    }
161
162    #[test]
163    fn single_source_is_used() {
164        let sel = select(&[src(0, 0.010, 0.002)]);
165        assert_eq!(sel.truechimers, vec![0]);
166        assert!((sel.offset.expect("offset") - 0.010).abs() < 1e-12);
167    }
168
169    #[test]
170    fn empty_input_is_empty_output() {
171        assert_eq!(select(&[]), Selection::default());
172    }
173}
rusty_time_core/select.rs

rusty_time_core/
select.rs
