denoland/celld

Public

Node lease takeover can overlap with the previous owner's local authority under clock skew

MI

I found a node-lease race where two owner epochs can authorize local work at the same time.

The lease deadline is written using the current owner's wall clock and checked using another node's wall clock. The old owner's self-fence uses its local monotonic clock. If the second machine's clock is ahead, it can treat the first lease as expired before the first machine fences itself. The owner CAS is atomic, but it cannot change the old owner's local authority state.

Concrete case:

- TTL: 10,000 ms - A creates its node lease at wall time 1,000,000 ms, writing `expires_ms = 1,010,000` - B's wall clock is 1,000 ms ahead - after 9,000 ms of real time, B reads 1,010,000 and advances the owner from A/epoch 1 to B/epoch 2 - A has measured only 9,000 ms on its monotonic clock, so it still routes a new request locally - B routes a new request locally at epoch 2 as well

```mermaid sequenceDiagram participant A as node A participant S as owner store participant B as node B (+1,000 ms)

A->>S: node lease expires_ms = 1,010,000 A->>S: owner = A / epoch 1 Note over A,B: 9,000 ms of real time passes Note over A: monotonic age = 9,000 ms<br/>still authoritative Note over B: wall clock = 1,010,000<br/>treats A as expired B->>S: CAS owner A/e1 → B/e2 S-->>B: Applied

par next request A->>A: Route::Local at epoch 1 and B->>B: Route::Local at epoch 2 end Note over A,B: two owner epochs authorize local work ```

I reproduced this through the public `State::on_event` API. On the vulnerable code, the final routes are `(Local, Local)`.

Abridged from the regression test:

```rust #[test] fn clock_skew_never_authorizes_two_owner_epochs() { const BASE_WALL_MS: u64 = 1_000_000; const B_WALL_OFFSET_MS: u64 = 1_000; const REAL_ELAPSED_MS: u64 = 9_000;

// A has already acquired owner epoch 1. let node_b_wall_ms = BASE_WALL_MS + REAL_ELAPSED_MS + B_WALL_OFFSET_MS; assert_eq!(node_b_wall_ms, node_a_lease.expires_ms);

let effects = on_event( &mut node_b, Event::NodeLeaseRead { op: lease_read_op, now_ms: node_b_wall_ms, result: Ok(Some(node_a_lease)), }, );

let Some((owner_cas_op, epoch, takeover)) = owner_cas(&effects) else { return; // fixed path keeps routing to A/e1 }; assert_eq!((epoch, takeover), (2, true)); finish_activation(&mut node_b, owner_cas_op, 2, 2);

// Both nodes receive another request at the same real elapsed time. let a_effects = on_event( &mut node_a, Event::RequestAt { request: 3, cell: CELL.into(), now_ms: BASE_WALL_MS + REAL_ELAPSED_MS, now_mono_ms: REAL_ELAPSED_MS, }, ); let b_effects = on_event( &mut node_b, Event::RequestAt { request: 4, cell: CELL.into(), now_ms: node_b_wall_ms, now_mono_ms: REAL_ELAPSED_MS, }, );

assert_ne!( (route_for(&a_effects, 3), route_for(&b_effects, 4)), (Some(Route::Local), Some(Route::Local)), ); } ```

Full investigation, trace, Quint model, and Rust regression test: https://gist.github.com/mizchi/58550e8d335a532f15d8e0cd84f57231

Reference implementation on my fork (no PR): https://github.com/mizchi/celld/commit/fa8163e3e34e5ea3fb0da3bc5181fd5a27fd2b18

Full reference branch: https://github.com/mizchi/celld/tree/experiment/quint-lease-clock

The minimal fix I tried is to keep a remote lease live through the supported clock-skew window, while enforcing the local monotonic deadline at every event boundary. This is only safe if the fleet skew bound is an actual operational contract. Alternatives are observing an unchanged lease ETag for a full monotonic TTL before takeover, or validating the owner epoch at write acknowledgement.

  1. Macilsubscribed3 months ago on GitHub

  2. BA

    Thanks for the report. This has been already fixed an will be released later this week in 0.2.0.

  3. bartlomiejuclosed3 months ago on GitHub