The engine consumes a raw log of (serverid, stratum, offset, round-trip delay, timestamp) samples and must (1) reject falsetickers, (2) refine the interval by stratum, (3) steer a local clock without oscillating. Four naive choices fail:
The verified solution is written to ~/ntp/SOLUTION.md, with the tested code in ~/ntp/ntp_engine.awk, ntp_engine.sh, and harness.sh. Full contents below.
The engine consumes a raw log of (server_id, stratum, offset, round-trip delay, timestamp) samples and must (1) reject falsetickers, (2) refine the interval by stratum, (3) steer a local clock without oscillating. Four naive choices fail:
| # | Naive approach | Failure mode |
|---|---|---|
| 1 | Average all offsets | Breakdown point 0: 3 colluding liars in 7 sources pull the mean by 3·δ/7. With δ = 1.5 s that is ≈ 642 ms — over the 500 ms budget. |
| 2 | max(lo)/min(hi) over all sources |
One liar widens/empties the interval. Marzullo finds the interval covered by the largest agreeing majority and rejects the rest. |
| 3 | Phase-only loop u = Kp·x |
A one-pole loop with integral action overshoots/rings. Critical damping (s² + 2ωs + ω²) needs a frequency state, which also cancels a static ppm skew. |
| 4 | dt = ts2 − ts1 on 32-bit era seconds |
Across 0xFFFFFFFF → 0 the difference is ≈ −4.29×10⁹ s instead of seconds — a sign flip that poisons the FLL. Must reduce mod 2³² into [−2³¹, 2³¹). |
With x = t − L (server minus corrected clock), x' = −(r + u). The hybrid controller is
c ← c + Kf·(dx + Kp·x) # FLL: frequency estimate from offset rate
u = c + Kp·x # PLL: phase correction on the frequency estimate
dx is in µs/s = ppm, c is the frequency correction estimate, u the applied rate. With Kp = 2ζω, ζ = 1 the closed loop is critically damped, so the response is monotone. Constants: ω = 0.01, Kp = 0.02, Kf = 0.1.
offset_us is measured against the free-running clock; the engine forms x = voted_offset − corr, so replay is independent of past corrections. timestamp_sec is always differenced with wrap32().
ntp_engine.awkfunction wrap32(d, m) {
m = d - 4294967296.0 * int(d / 4294967296.0);
if (m < 0) m += 4294967296.0;
if (m >= 2147483648.0) m -= 4294967296.0;
return m;
}
function flush( i, j, k, ec, tmp, tj, cnt, best, bs, be, state,
sw, sc, shw, nt, center, hw, w, rlo, rhi, voted,
mean, half, dt, ts_cur, ax) {
if (nr == 0) return;
for (i = 0; i < nr; i++) { half = delay[i]/2.0; lo[i]=off[i]-half; hi[i]=off[i]+half; }
ec = 0;
for (i = 0; i < nr; i++) {
ec++; ev[ec]=lo[i]; ed[ec]= 1;
ec++; ev[ec]=hi[i]; ed[ec]=-1;
}
for (i = 2; i <= ec; i++) {
tmp=ev[i]; tj=ed[i]; j=i-1;
while (j>=1 && (ev[j]>tmp || (ev[j]==tmp && ed[j]<tj))) { ev[j+1]=ev[j]; ed[j+1]=ed[j]; j--; }
ev[j+1]=tmp; ed[j+1]=tj;
}
cnt=0; best=0; bs=0; be=0; inregion=0;
for (i = 1; i <= ec; i++) {
if (ed[i]==1) {
cnt++;
if (cnt>best) { best=cnt; bs=ev[i]; be=ev[i]; inregion=1; }
else if (inregion && cnt==best) be=ev[i];
} else {
if (inregion && cnt==best) be=ev[i];
cnt--;
if (inregion && cnt<best) inregion=0;
}
}
mean=0; for (i=0;i<nr;i++) mean+=off[i]; mean/=nr;
sw=0; sc=0; nt=0;
for (i=0;i<nr;i++) if (lo[i]<=be && hi[i]>=bs) { w=1.0/stratum[i]; sw+=w; sc+=w*off[i]; nt++; }
if (sw>0) {
wmean=sc/sw; sv=0;
for (i=0;i<nr;i++) if (lo[i]<=be && hi[i]>=bs)
sv += (1.0/stratum[i])*(off[i]-wmean)*(off[i]-wmean);
whw=sqrt(sv/sw);
rlo=wmean-whw; rhi=wmean+whw;
if (rlo<bs) rlo=bs; if (rhi>be) rhi=be;
if (rlo>rhi) { rlo=bs; rhi=be; }
} else { rlo=bs; rhi=be; }
voted=(rlo+rhi)/2.0;
ts_cur=timestamp[0];
if (have_ts) dt=wrap32(ts_cur-last_ts); else dt=0;
have_ts=1; last_ts=ts_cur;
if (mode=="steer") {
if (dt<=0) dt=1;
if (!have_x) { x=0; have_x=1; } else x=voted-corr;
dx = have_px ? (x-xprev)/dt : 0;
c += Kf*(dx + Kp*x);
u = c + Kp*x;
corr += u*dt;
xprev=x; have_px=1; elapsed+=dt;
}
printf "ROUND round=%s n=%d lo_us=%.3f hi_us=%.3f nf=%d truechimers=%d ", cur_round,nr,bs,be,nr-best,nt;
printf "center_us=%.3f mean_us=%.3f refined_lo_us=%.3f refined_hi_us=%.3f ", (bs+be)/2.0,mean,rlo,rhi;
printf "ts=%.0f dt=%.3f", ts_cur, dt;
if (mode=="steer") printf " res_us=%.6f freq_ppm=%.6f corr_us=%.3f elapsed=%.3f", x,c,corr,elapsed;
printf "\n"; nr=0;
}
BEGIN {
if (mode=="") mode="vote";
if (omega==0) omega=0.01;
Kp=2.0*omega; Kf=0.1;
nr=0; cur_round=""; have_ts=0; have_x=0; have_px=0; corr=0; c=0; xprev=0; elapsed=0;
}
/^[[:space:]]*#/ || NF==0 { next }
{
r=$1+0;
if (r!=cur_round) { if (cur_round!="") flush(); cur_round=r; }
sid[nr]=$2+0; stratum[nr]=$3+0; off[nr]=$4+0; delay[nr]=$5+0; timestamp[nr]=$6+0; nr++;
}
END { if (cur_round!="") flush(); }
ntp_engine.sh#!/usr/bin/env bash
set -euo pipefail
DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
exec awk -f "$DIR/ntp_engine.awk" "$@"
harness.sh#!/usr/bin/env bash
set -euo pipefail
DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
ENGINE=(awk -f "$DIR/ntp_engine.awk")
WORK="$(mktemp -d)"; trap 'rm -rf "$WORK"' EXIT
fail=0
note() { printf '%s\n' "$*"; }
check() { if [ "$2" = "1" ]; then printf ' [PASS] %s -- %s\n' "$1" "$3"; else printf ' [FAIL] %s -- %s\n' "$1" "$3"; fail=1; fi; }
note "== Scenario 1: Marzullo majority vote vs. averaging =="
cat > "$WORK/vote.log" <<'EOF'
# round server stratum offset_us delay_us timestamp
1 1 1 0 1000 3900000000
1 2 2 200 800 3900000000
1 3 3 -150 600 3900000000
1 4 1 300 1200 3900000000
1 5 1 1500000 900 3900000000
1 6 2 1500200 700 3900000000
1 7 3 1499800 1100 3900000000
EOF
"${ENGINE[@]}" -v mode=vote "$WORK/vote.log" > "$WORK/vote.out"; cat "$WORK/vote.out"
read -r mean center lo hi nf rlo rhi < <(awk '/^ROUND/{for(i=1;i<=NF;i++){split($i,a,"=");m[a[1]]=a[2]}
print m["mean_us"],m["center_us"],m["lo_us"],m["hi_us"],m["nf"],m["refined_lo_us"],m["refined_hi_us"]}' "$WORK/vote.out")
abs_mean=${mean#-}
check "averaged voter dragged off truth" "$(awk -v v="$abs_mean" 'BEGIN{print (v>500000)?1:0}')" \
"mean offset = $(awk -v v="$abs_mean" 'BEGIN{printf "%.3f ms",v/1000}') from truth (limit 500 ms)"
check "intersection vote inside honest interval" "$(awk -v l="$lo" -v h="$hi" 'BEGIN{print (l<=0&&0<=h)?1:0}')" \
"consensus interval = [$(awk -v v="$lo" 'BEGIN{printf "%.3f",v/1000}'), $(awk -v v="$hi" 'BEGIN{printf "%.3f",v/1000}')] ms contains truth 0"
check "intersection vote near truth" "$(awk -v c="$center" 'BEGIN{v=(c<0?-c:c);print (v<1000)?1:0}')" \
"intersection offset = $(awk -v v="$center" 'BEGIN{printf "%.3f ms",v/1000}') (limit 1 ms)"
check "falsetickers identified" "$([ "$nf" = "3" ] && echo 1 || echo 0)" "$nf falsetickers rejected (expected 3)"
check "stratum-weighted interval narrowed" "$(awk -v a="$lo" -v b="$hi" -v c="$rlo" -v d="$rhi" 'BEGIN{print (d-c<=b-a)?1:0}')" \
"width $(awk -v a="$lo" -v b="$hi" -v c="$rlo" -v d="$rhi" 'BEGIN{printf "%.3f ms -> %.3f ms",(b-a)/1000,(d-c)/1000}') after weighting"
check "refined interval stays inside honest interval" "$(awk -v l="$rlo" -v h="$rhi" 'BEGIN{print (l<=0&&0<=h)?1:0}')" \
"refined interval = [$(awk -v v="$rlo" 'BEGIN{printf "%.3f",v/1000}'), $(awk -v v="$rhi" 'BEGIN{printf "%.3f",v/1000}')] ms contains truth 0"
note; note "== Scenario 2: hybrid PLL/FLL steering from 500 ppm =="
awk 'BEGIN{r0=500e-6; for(k=0;k<2100;k++){ts=3900000000+k; off=-r0*k*1e6;
for(j=0;j<7;j++){printf "%d %d %d %.3f %d %.0f\n",k+1,j+1,(j%3)+1,off+(j-3)*10,200,ts;}}}' > "$WORK/steer.log"
"${ENGINE[@]}" -v mode=steer "$WORK/steer.log" > "$WORK/steer.out"
read -r maxres res2000 freq2000 lastbad lastbadf npos maxpos < <(
awk '/^ROUND/{for(i=1;i<=NF;i++){split($i,a,"=");m[a[1]]=a[2]}
t=m["ts"]-3900000000; r=m["res_us"]; ar=(r<0?-r:r); f=m["freq_ppm"]+500; if(f<0)f=-f;
if(t>=2000&&ar>maxres)maxres=ar; if(t==2000){res2000=m["res_us"];freq2000=m["freq_ppm"];}
if(ar>=1000)lastbad=t; if(f>=1)lastbadf=t; if(r>0)npos++; if(r>maxpos)maxpos=r;}
END{printf "%.6f %.6f %.6f %d %d %d %.6f\n",maxres,res2000,freq2000,lastbad,lastbadf,npos,maxpos}' "$WORK/steer.out")
note " residual@2000s = $res2000 us freq@2000s = $freq2000 ppm max|residual|[2000,2099] = $maxres us"
note " |residual| < 1 ms for t > $lastbad s |freq+500| < 1 ppm for t > $lastbadf s overshoot samples = $npos"
check "residual < 1 ms at t=2000 s" "$(awk -v r="$res2000" 'BEGIN{v=(r<0?-r:r);print (v<1000)?1:0}')" \
"|residual| = $(awk -v v="$res2000" 'BEGIN{printf "%.6f ms",(v<0?-v:v)/1000}')"
check "residual stays < 1 ms" "$(awk -v r="$maxres" 'BEGIN{print (r<1000)?1:0}')" \
"max |residual| = $(awk -v v="$maxres" 'BEGIN{printf "%.6f ms",v/1000}')"
check "residual settles < 1 ms within 2000 s" "$(awk -v t="${lastbad:-0}" 'BEGIN{print (t<2000)?1:0}')" \
"last |residual| >= 1 ms at t=${lastbad:-0} s"
check "frequency settles within 2000 s" "$(awk -v t="${lastbadf:-0}" 'BEGIN{print (t<2000)?1:0}')" \
"frequency settled to -500 ppm by t=${lastbadf:-0} s (estimate $freq2000 ppm)"
check "no overshoot / no oscillation" "$(awk -v n="${npos:-0}" -v m="${maxpos:-0}" 'BEGIN{print (n==0&&m==0)?1:0}')" \
"$npos samples above target, max overshoot $(awk -v v="${maxpos:-0}" 'BEGIN{printf "%.6f us",v}')"
note; note "== Scenario 3: 2^32-second era-wrap timestamp =="
cat > "$WORK/era.log" <<'EOF'
# round server stratum offset_us delay_us timestamp
1 1 1 0 200 4294967200
1 2 1 0 200 4294967200
2 1 1 0 200 96
2 2 1 0 200 96
EOF
"${ENGINE[@]}" -v mode=vote "$WORK/era.log" > "$WORK/era.out"; cat "$WORK/era.out"
dt2=$(awk '/^ROUND/{for(i=1;i<=NF;i++){split($i,a,"=");m[a[1]]=a[2]}} m["round"]==2{print m["dt"]}' "$WORK/era.out" | tail -1)
check "wrap-safe positive dt" "$(awk -v d="$dt2" 'BEGIN{print (d==192)?1:0}')" \
"dt across wrap = ${dt2} s (expected 192, no sign flip)"
note; if [ "$fail" = "0" ]; then note "RESULT: ALL CHECKS PASSED"; else note "RESULT: FAILURES PRESENT"; fi
exit "$fail"
== Scenario 1: Marzullo majority vote vs. averaging ==
ROUND round=1 n=7 lo_us=-200.000 hi_us=150.000 nf=3 truechimers=4 center_us=-25.000 mean_us=642907.143 refined_lo_us=-38.369 refined_hi_us=150.000 ts=3900000000 dt=0.000
[PASS] averaged voter dragged off truth -- mean offset = 642.907 ms from truth (limit 500 ms)
[PASS] intersection vote inside honest interval -- consensus interval = [-0.200, 0.150] ms contains truth 0
[PASS] intersection vote near truth -- intersection offset = -0.025 ms (limit 1 ms)
[PASS] falsetickers identified -- 3 falsetickers rejected (expected 3)
[PASS] stratum-weighted interval narrowed -- width 0.350 ms -> 0.188 ms after weighting
[PASS] refined interval stays inside honest interval -- refined interval = [-0.038, 0.150] ms contains truth 0
== Scenario 2: hybrid PLL/FLL steering from 500 ppm ==
residual@2000s = 0.000000 us freq@2000s = -500.000000 ppm max|residual|[2000,2099] = 0.000000 us
|residual| < 1 ms for t > 91 s |freq+500| < 1 ppm for t > 69 s overshoot samples = 0
[PASS] residual < 1 ms at t=2000 s -- |residual| = 0.000000 ms
[PASS] residual stays < 1 ms -- max |residual| = 0.000000 ms
[PASS] residual settles < 1 ms within 2000 s -- last |residual| >= 1 ms at t=91 s
[PASS] frequency settles within 2000 s -- frequency settled to -500 ppm by t=69 s (estimate -500.000000 ppm)
[PASS] no overshoot / no oscillation -- 0 samples above target, max overshoot 0.000000 us
== Scenario 3: 2^32-second era-wrap timestamp ==
ROUND round=1 n=2 lo_us=-100.000 hi_us=100.000 nf=0 truechimers=2 center_us=0.000 mean_us=0.000 refined_lo_us=0.000 refined_hi_us=0.000 ts=4294967200 dt=0.000
ROUND round=2 n=2 lo_us=-100.000 hi_us=100.000 nf=0 truechimers=2 center_us=0.000 mean_us=0.000 refined_lo_us=0.000 refined_hi_us=0.000 ts=96 dt=192.000
[PASS] wrap-safe positive dt -- dt across wrap = 192.000 s (expected 192, no sign flip)
RESULT: ALL CHECKS PASSED
What each result proves
- Falsetickers: averaging is dragged 642.907 ms off truth (> 500 ms), while Marzullo's interval [-0.200, 0.150] ms contains truth and its centre is 25 µs off; exactly 3 liars rejected.
- Refinement: 1/stratum weighting narrows the majority interval 0.350 ms → 0.188 ms, still containing truth.
- Steering: from 500 ppm, |residual| < 1 ms for all t > 91 s, frequency reaches -500.000000 ppm by t = 69 s, with 0 overshoot samples — critically damped, no ring.
- Era wrap: 4294967200 → 96 gives dt = 192 s, not −4294967104 s; wrap spot checks 4294967295 → 1 = 2 s and 100 → 4294967196 = −200 s.
-v omega=0.02 to change loop bandwidth; Kp = 2·omega keeps critical damping. Kf = 0.1; ≈1.0 destabilizes the discrete loop.truechimers > n/2 before disciplining; the sweep currently returns the max-overlap region with nf reported.# Evidence - Problem class: bash-marzullo-falseticker-ntp-steering-loop - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-23T16:28:00.777Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an NTP-style clock-discipline engine in bash/awk that reads a raw measurement log of (server_id, stratum, offset, round-trip delay, timestamp) samples and performs three things: outlier rejection by Marzullo/intersection-interval majority voting to identify falsetickers, refinement of the true interval by stratum-weighted intersection narrowing, and steering of a local clock with a hybrid PLL/FLL loop (phase gain plus frequency estimate) that must not oscillate or overshoot. Prove with a deterministic replay harness that with 7 sources of which 3 are colluding liars an averaged-offset voter is dragged more than 500 ms off truth while the intersection vote stays inside the honest interval; that the steering loop converges to under 1 ms residual and settles frequency within 2000 s from an initial 500 ppm skew; and that a 2^32-second era-wrap timestamp in the log is handled without a sign flip. Deliver the script plus the harness and the printed metrics.", "environment": "bash", "language": "bash", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-marzullo-falseticker-ntp-steering-loop", "provider": "openrouter", "solved_at": "2026-09-23T16:28:00.777Z", "version": "5.2"}The verified solution is written to ~/ntp/SOLUTION.md, with the tested code in ~/ntp/ntp_engine.awk, ntp_engine.sh, and harness.sh. Full contents below.
The engine consumes a raw log of (server_id, stratum, offset, round-trip delay, timestamp) samples and must (1) reject falsetickers, (2) refine the interval by stratum, (3) steer a local clock without oscillating. Four naive choices fail:
| # | Naive approach | Failure mode |
|---|---|---|
| 1 | Average all offsets | Breakdown point 0: 3 colluding liars in 7 sources pull the mean by 3·δ/7. With δ = 1.5 s that is ≈ 642 ms — over the 500 ms budget. |
| 2 | max(lo)/min(hi) over all sources |
One liar widens/empties the interval. Marzullo finds the interval covered by the largest agreeing majority and rejects the rest. |
| 3 | Phase-only loop u = Kp·x |
A one-pole loop with integral action overshoots/rings. Critical damping (s² + 2ωs + ω²) needs a frequency state, which also cancels a static ppm skew. |
| 4 | dt = ts2 − ts1 on 32-bit era seconds |
Across 0xFFFFFFFF → 0 the difference is ≈ −4.29×10⁹ s instead of seconds — a sign flip that poisons the FLL. Must reduce mod 2³² into [−2³¹, 2³¹). |
With x = t − L (server minus corrected clock), x' = −(r + u). The hybrid controller is
c ← c + Kf·(dx + Kp·x) # FLL: frequency estimate from offset rate
u = c + Kp·x # PLL: phase correction on the frequency estimate
dx is in µs/s = ppm, c is the frequency correction estimate, u the applied rate. With Kp = 2ζω, ζ = 1 the closed loop is critically damped, so the response is monotone. Constants: ω = 0.01, Kp = 0.02, Kf = 0.1.
offset_us is measured against the free-running clock; the engine forms x = voted_offset − corr, so replay is independent of past corrections. timestamp_sec is always differenced with wrap32().
ntp_engine.awkfunction wrap32(d, m) {
m = d - 4294967296.0 * int(d / 4294967296.0);
if (m < 0) m += 4294967296.0;
if (m >= 2147483648.0) m -= 4294967296.0;
return m;
}
function flush( i, j, k, ec, tmp, tj, cnt, best, bs, be, state,
sw, sc, shw, nt, center, hw, w, rlo, rhi, voted,
mean, half, dt, ts_cur, ax) {
if (nr == 0) return;
for (i = 0; i < nr; i++) { half = delay[i]/2.0; lo[i]=off[i]-half; hi[i]=off[i]+half; }
ec = 0;
for (i = 0; i < nr; i++) {
ec++; ev[ec]=lo[i]; ed[ec]= 1;
ec++; ev[ec]=hi[i]; ed[ec]=-1;
}
for (i = 2; i <= ec; i++) {
tmp=ev[i]; tj=ed[i]; j=i-1;
while (j>=1 && (ev[j]>tmp || (ev[j]==tmp && ed[j]<tj))) { ev[j+1]=ev[j]; ed[j+1]=ed[j]; j--; }
ev[j+1]=tmp; ed[j+1]=tj;
}
cnt=0; best=0; bs=0; be=0; inregion=0;
for (i = 1; i <= ec; i++) {
if (ed[i]==1) {
cnt++;
if (cnt>best) { best=cnt; bs=ev[i]; be=ev[i]; inregion=1; }
else if (inregion && cnt==best) be=ev[i];
} else {
if (inregion && cnt==best) be=ev[i];
cnt--;
if (inregion && cnt<best) inregion=0;
}
}
mean=0; for (i=0;i<nr;i++) mean+=off[i]; mean/=nr;
sw=0; sc=0; nt=0;
for (i=0;i<nr;i++) if (lo[i]<=be && hi[i]>=bs) { w=1.0/stratum[i]; sw+=w; sc+=w*off[i]; nt++; }
if (sw>0) {
wmean=sc/sw; sv=0;
for (i=0;i<nr;i++) if (lo[i]<=be && hi[i]>=bs)
sv += (1.0/stratum[i])*(off[i]-wmean)*(off[i]-wmean);
whw=sqrt(sv/sw);
rlo=wmean-whw; rhi=wmean+whw;
if (rlo<bs) rlo=bs; if (rhi>be) rhi=be;
if (rlo>rhi) { rlo=bs; rhi=be; }
} else { rlo=bs; rhi=be; }
voted=(rlo+rhi)/2.0;
ts_cur=timestamp[0];
if (have_ts) dt=wrap32(ts_cur-last_ts); else dt=0;
have_ts=1; last_ts=ts_cur;
if (mode=="steer") {
if (dt<=0) dt=1;
if (!have_x) { x=0; have_x=1; } else x=voted-corr;
dx = have_px ? (x-xprev)/dt : 0;
c += Kf*(dx + Kp*x);
u = c + Kp*x;
corr += u*dt;
xprev=x; have_px=1; elapsed+=dt;
}
printf "ROUND round=%s n=%d lo_us=%.3f hi_us=%.3f nf=%d truechimers=%d ", cur_round,nr,bs,be,nr-best,nt;
printf "center_us=%.3f mean_us=%.3f refined_lo_us=%.3f refined_hi_us=%.3f ", (bs+be)/2.0,mean,rlo,rhi;
printf "ts=%.0f dt=%.3f", ts_cur, dt;
if (mode=="steer") printf " res_us=%.6f freq_ppm=%.6f corr_us=%.3f elapsed=%.3f", x,c,corr,elapsed;
printf "\n"; nr=0;
}
BEGIN {
if (mode=="") mode="vote";
if (omega==0) omega=0.01;
Kp=2.0*omega; Kf=0.1;
nr=0; cur_round=""; have_ts=0; have_x=0; have_px=0; corr=0; c=0; xprev=0; elapsed=0;
}
/^[[:space:]]*#/ || NF==0 { next }
{
r=$1+0;
if (r!=cur_round) { if (cur_round!="") flush(); cur_round=r; }
sid[nr]=$2+0; stratum[nr]=$3+0; off[nr]=$4+0; delay[nr]=$5+0; timestamp[nr]=$6+0; nr++;
}
END { if (cur_round!="") flush(); }
ntp_engine.sh#!/usr/bin/env bash
set -euo pipefail
DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
exec awk -f "$DIR/ntp_engine.awk" "$@"
harness.sh#!/usr/bin/env bash
set -euo pipefail
DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
ENGINE=(awk -f "$DIR/ntp_engine.awk")
WORK="$(mktemp -d)"; trap 'rm -rf "$WORK"' EXIT
fail=0
note() { printf '%s\n' "$*"; }
check() { if [ "$2" = "1" ]; then printf ' [PASS] %s -- %s\n' "$1" "$3"; else printf ' [FAIL] %s -- %s\n' "$1" "$3"; fail=1; fi; }
note "== Scenario 1: Marzullo majority vote vs. averaging =="
cat > "$WORK/vote.log" <<'EOF'
# round server stratum offset_us delay_us timestamp
1 1 1 0 1000 3900000000
1 2 2 200 800 3900000000
1 3 3 -150 600 3900000000
1 4 1 300 1200 3900000000
1 5 1 1500000 900 3900000000
1 6 2 1500200 700 3900000000
1 7 3 1499800 1100 3900000000
EOF
"${ENGINE[@]}" -v mode=vote "$WORK/vote.log" > "$WORK/vote.out"; cat "$WORK/vote.out"
read -r mean center lo hi nf rlo rhi < <(awk '/^ROUND/{for(i=1;i<=NF;i++){split($i,a,"=");m[a[1]]=a[2]}
print m["mean_us"],m["center_us"],m["lo_us"],m["hi_us"],m["nf"],m["refined_lo_us"],m["refined_hi_us"]}' "$WORK/vote.out")
abs_mean=${mean#-}
check "averaged voter dragged off truth" "$(awk -v v="$abs_mean" 'BEGIN{print (v>500000)?1:0}')" \
"mean offset = $(awk -v v="$abs_mean" 'BEGIN{printf "%.3f ms",v/1000}') from truth (limit 500 ms)"
check "intersection vote inside honest interval" "$(awk -v l="$lo" -v h="$hi" 'BEGIN{print (l<=0&&0<=h)?1:0}')" \
"consensus interval = [$(awk -v v="$lo" 'BEGIN{printf "%.3f",v/1000}'), $(awk -v v="$hi" 'BEGIN{printf "%.3f",v/1000}')] ms contains truth 0"
check "intersection vote near truth" "$(awk -v c="$center" 'BEGIN{v=(c<0?-c:c);print (v<1000)?1:0}')" \
"intersection offset = $(awk -v v="$center" 'BEGIN{printf "%.3f ms",v/1000}') (limit 1 ms)"
check "falsetickers identified" "$([ "$nf" = "3" ] && echo 1 || echo 0)" "$nf falsetickers rejected (expected 3)"
check "stratum-weighted interval narrowed" "$(awk -v a="$lo" -v b="$hi" -v c="$rlo" -v d="$rhi" 'BEGIN{print (d-c<=b-a)?1:0}')" \
"width $(awk -v a="$lo" -v b="$hi" -v c="$rlo" -v d="$rhi" 'BEGIN{printf "%.3f ms -> %.3f ms",(b-a)/1000,(d-c)/1000}') after weighting"
check "refined interval stays inside honest interval" "$(awk -v l="$rlo" -v h="$rhi" 'BEGIN{print (l<=0&&0<=h)?1:0}')" \
"refined interval = [$(awk -v v="$rlo" 'BEGIN{printf "%.3f",v/1000}'), $(awk -v v="$rhi" 'BEGIN{printf "%.3f",v/1000}')] ms contains truth 0"
note; note "== Scenario 2: hybrid PLL/FLL steering from 500 ppm =="
awk 'BEGIN{r0=500e-6; for(k=0;k<2100;k++){ts=3900000000+k; off=-r0*k*1e6;
for(j=0;j<7;j++){printf "%d %d %d %.3f %d %.0f\n",k+1,j+1,(j%3)+1,off+(j-3)*10,200,ts;}}}' > "$WORK/steer.log"
"${ENGINE[@]}" -v mode=steer "$WORK/steer.log" > "$WORK/steer.out"
read -r maxres res2000 freq2000 lastbad lastbadf npos maxpos < <(
awk '/^ROUND/{for(i=1;i<=NF;i++){split($i,a,"=");m[a[1]]=a[2]}
t=m["ts"]-3900000000; r=m["res_us"]; ar=(r<0?-r:r); f=m["freq_ppm"]+500; if(f<0)f=-f;
if(t>=2000&&ar>maxres)maxres=ar; if(t==2000){res2000=m["res_us"];freq2000=m["freq_ppm"];}
if(ar>=1000)lastbad=t; if(f>=1)lastbadf=t; if(r>0)npos++; if(r>maxpos)maxpos=r;}
END{printf "%.6f %.6f %.6f %d %d %d %.6f\n",maxres,res2000,freq2000,lastbad,lastbadf,npos,maxpos}' "$WORK/steer.out")
note " residual@2000s = $res2000 us freq@2000s = $freq2000 ppm max|residual|[2000,2099] = $maxres us"
note " |residual| < 1 ms for t > $lastbad s |freq+500| < 1 ppm for t > $lastbadf s overshoot samples = $npos"
check "residual < 1 ms at t=2000 s" "$(awk -v r="$res2000" 'BEGIN{v=(r<0?-r:r);print (v<1000)?1:0}')" \
"|residual| = $(awk -v v="$res2000" 'BEGIN{printf "%.6f ms",(v<0?-v:v)/1000}')"
check "residual stays < 1 ms" "$(awk -v r="$maxres" 'BEGIN{print (r<1000)?1:0}')" \
"max |residual| = $(awk -v v="$maxres" 'BEGIN{printf "%.6f ms",v/1000}')"
check "residual settles < 1 ms within 2000 s" "$(awk -v t="${lastbad:-0}" 'BEGIN{print (t<2000)?1:0}')" \
"last |residual| >= 1 ms at t=${lastbad:-0} s"
check "frequency settles within 2000 s" "$(awk -v t="${lastbadf:-0}" 'BEGIN{print (t<2000)?1:0}')" \
"frequency settled to -500 ppm by t=${lastbadf:-0} s (estimate $freq2000 ppm)"
check "no overshoot / no oscillation" "$(awk -v n="${npos:-0}" -v m="${maxpos:-0}" 'BEGIN{print (n==0&&m==0)?1:0}')" \
"$npos samples above target, max overshoot $(awk -v v="${maxpos:-0}" 'BEGIN{printf "%.6f us",v}')"
note; note "== Scenario 3: 2^32-second era-wrap timestamp =="
cat > "$WORK/era.log" <<'EOF'
# round server stratum offset_us delay_us timestamp
1 1 1 0 200 4294967200
1 2 1 0 200 4294967200
2 1 1 0 200 96
2 2 1 0 200 96
EOF
"${ENGINE[@]}" -v mode=vote "$WORK/era.log" > "$WORK/era.out"; cat "$WORK/era.out"
dt2=$(awk '/^ROUND/{for(i=1;i<=NF;i++){split($i,a,"=");m[a[1]]=a[2]}} m["round"]==2{print m["dt"]}' "$WORK/era.out" | tail -1)
check "wrap-safe positive dt" "$(awk -v d="$dt2" 'BEGIN{print (d==192)?1:0}')" \
"dt across wrap = ${dt2} s (expected 192, no sign flip)"
note; if [ "$fail" = "0" ]; then note "RESULT: ALL CHECKS PASSED"; else note "RESULT: FAILURES PRESENT"; fi
exit "$fail"
== Scenario 1: Marzullo majority vote vs. averaging ==
ROUND round=1 n=7 lo_us=-200.000 hi_us=150.000 nf=3 truechimers=4 center_us=-25.000 mean_us=642907.143 refined_lo_us=-38.369 refined_hi_us=150.000 ts=3900000000 dt=0.000
[PASS] averaged voter dragged off truth -- mean offset = 642.907 ms from truth (limit 500 ms)
[PASS] intersection vote inside honest interval -- consensus interval = [-0.200, 0.150] ms contains truth 0
[PASS] intersection vote near truth -- intersection offset = -0.025 ms (limit 1 ms)
[PASS] falsetickers identified -- 3 falsetickers rejected (expected 3)
[PASS] stratum-weighted interval narrowed -- width 0.350 ms -> 0.188 ms after weighting
[PASS] refined interval stays inside honest interval -- refined interval = [-0.038, 0.150] ms contains truth 0
== Scenario 2: hybrid PLL/FLL steering from 500 ppm ==
residual@2000s = 0.000000 us freq@2000s = -500.000000 ppm max|residual|[2000,2099] = 0.000000 us
|residual| < 1 ms for t > 91 s |freq+500| < 1 ppm for t > 69 s overshoot samples = 0
[PASS] residual < 1 ms at t=2000 s -- |residual| = 0.000000 ms
[PASS] residual stays < 1 ms -- max |residual| = 0.000000 ms
[PASS] residual settles < 1 ms within 2000 s -- last |residual| >= 1 ms at t=91 s
[PASS] frequency settles within 2000 s -- frequency settled to -500 ppm by t=69 s (estimate -500.000000 ppm)
[PASS] no overshoot / no oscillation -- 0 samples above target, max overshoot 0.000000 us
== Scenario 3: 2^32-second era-wrap timestamp ==
ROUND round=1 n=2 lo_us=-100.000 hi_us=100.000 nf=0 truechimers=2 center_us=0.000 mean_us=0.000 refined_lo_us=0.000 refined_hi_us=0.000 ts=4294967200 dt=0.000
ROUND round=2 n=2 lo_us=-100.000 hi_us=100.000 nf=0 truechimers=2 center_us=0.000 mean_us=0.000 refined_lo_us=0.000 refined_hi_us=0.000 ts=96 dt=192.000
[PASS] wrap-safe positive dt -- dt across wrap = 192.000 s (expected 192, no sign flip)
RESULT: ALL CHECKS PASSED
What each result proves
- Falsetickers: averaging is dragged 642.907 ms off truth (> 500 ms), while Marzullo's interval [-0.200, 0.150] ms contains truth and its centre is 25 µs off; exactly 3 liars rejected.
- Refinement: 1/stratum weighting narrows the majority interval 0.350 ms → 0.188 ms, still containing truth.
- Steering: from 500 ppm, |residual| < 1 ms for all t > 91 s, frequency reaches -500.000000 ppm by t = 69 s, with 0 overshoot samples — critically damped, no ring.
- Era wrap: 4294967200 → 96 gives dt = 192 s, not −4294967104 s; wrap spot checks 4294967295 → 1 = 2 s and 100 → 4294967196 = −200 s.
-v omega=0.02 to change loop bandwidth; Kp = 2·omega keeps critical damping. Kf = 0.1; ≈1.0 destabilizes the discrete loop.truechimers > n/2 before disciplining; the sweep currently returns the max-overlap region with nf reported.# Evidence - Problem class: bash-marzullo-falseticker-ntp-steering-loop - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-23T16:28:00.777Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an NTP-style clock-discipline engine in bash/awk that reads a raw measurement log of (server_id, stratum, offset, round-trip delay, timestamp) samples and performs three things: outlier rejection by Marzullo/intersection-interval majority voting to identify falsetickers, refinement of the true interval by stratum-weighted intersection narrowing, and steering of a local clock with a hybrid PLL/FLL loop (phase gain plus frequency estimate) that must not oscillate or overshoot. Prove with a deterministic replay harness that with 7 sources of which 3 are colluding liars an averaged-offset voter is dragged more than 500 ms off truth while the intersection vote stays inside the honest interval; that the steering loop converges to under 1 ms residual and settles frequency within 2000 s from an initial 500 ppm skew; and that a 2^32-second era-wrap timestamp in the log is handled without a sign flip. Deliver the script plus the harness and the printed metrics.", "environment": "bash", "language": "bash", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-marzullo-falseticker-ntp-steering-loop", "provider": "openrouter", "solved_at": "2026-09-23T16:28:00.777Z", "version": "5.2"}