Membership & Reconfiguration: Changing the Set Without Breaking Safety

Monthly research note. Theme: Distributed Systems Under Failure.

TL;DR

A focused memo on Membership & Reconfiguration: Changing the Set Without Breaking Safety: define the model, state the properties, then design the system so those properties remain true under failure and adversaries.

Key takeaways

• Write the safety property first; liveness is always conditional on timing assumptions.
• Treat membership changes and compaction as protocol events—not operational details.
• Mixed-version operation is the default; upgrades must preserve invariants.
• Treat retries, reordering, and partial failure as default conditions.
• Make failure modes explicit and observable.

Why this matters

• Safety failures are permanent; liveness failures are (sometimes) recoverable.
• Most protocol bugs hide in timeouts, retries, and membership changes.
• State compaction and snapshots are where correctness goes to die quietly.
• Observability must explain protocol state, not just latency.

Key questions

• Where do you pay for liveness (timeouts, leader election, reconfiguration)?
• What does “read” mean under replication lag?
• What is the failure model (crash, byzantine, partitions, reordering)?
• What is your reconfiguration model (joint consensus, epochs, leases)?
• How do clients discover leaders safely (and what happens during flaps)?
• Which components require determinism for reproducibility?

Assumptions

• Packets can be duplicated and reordered; acks can be lost.
• Clients retry and amplify load right when the system is weakest.
• Nodes restart with partial state unless you prove durability.
• Workload is skewed: hot keys exist and dominate.

Non-goals

• Pretending backpressure is an implementation detail.
• Relying on global time for ordering without strong synchronization assumptions.

Model & invariants

A common safety shape for replicated logs:

Treat membership changes as protocol events, not control-plane side effects.

Make overload explicit: admission control is a protocol boundary.

Security properties

• Least authority: privileges are scoped by purpose and time.
• Authenticity: actions are bound to identity and purpose.
• Downgrade resistance: negotiation can’t silently weaken security posture.
• Evidence: critical actions emit verifiable audit events.

Failure modes

• Resource exhaustion (CPU/bandwidth/storage) turning into correctness failures.
• Mixed-version behavior that violates assumptions silently.
• Recovery paths that only work when nothing is broken.
• Timeout ambiguity causing double-apply or partial state transitions.

Design sketch

flowchart TD
  client["Client"] --> leader["Leader"]
  leader --> log["Replicated Log"]
  log --> snap["Snapshot"]
  snap --> recover["Recovery / Catch-up"]
  leader --> reconfig["Reconfiguration"]

Implementation notes

Your protocol is an interface between failures and invariants. Encode both.

type LogIndex = u64;

#[derive(Clone, Debug)]
struct Entry {
  index: LogIndex,
  term: u64,
  bytes: Vec<u8>,
}

// Persist(term, vote, log) before acknowledging anything.

Verification strategy

• Linearizability checks for read/write APIs that claim it.
• Upgrade tests: mixed versions and rolling deploy invariants.
• Model checking the smallest core (timeouts, election, reconfiguration).
• Jepsen-style fault injection: partitions + reordering + client retries.
• Stress + skew tests: hot keys, slow disks, noisy neighbors.

Operational notes

• Expose protocol state: term/epoch, leader, commit index, config version.
• Prefer monotonic time sources for leases; alert on clock discontinuities.
• Rate-limit retries and apply admission control before saturation.
• Rehearse region failover and reconfiguration under load.
• Make client behavior part of the system: document retry semantics.

What to monitor

• Retry/timeout rates by endpoint and client cohort.
• Invariant violation rate (should be ~0).
• Rollback events and the conditions that triggered them.
• Admission-control / rate-limit rejections (by reason).
• Authz failures and policy denials (unexpected spikes).

Rollback plan

• Prefer backward-compatible changes; avoid “flag day” upgrades.
• Keep dual-write / dual-verify windows where appropriate.
• Use canaries and staged rollout; stop early when signals degrade.
• Preserve evidence (configs, artifacts, audit logs) to reconstruct what changed.
• Define an explicit rollback trigger (metrics + thresholds).

Evidence

• In Search of an Understandable Consensus Algorithm (Raft) (1) — Consensus with explicit state machines and practical tradeoffs.
  • Evidence: Track term/commitIndex as explicit evidence; test leader changes and log conflicts as part of rollback behavior.
• Jepsen (2) — Testing correctness under partitions and faults.
  • Evidence: Turn faults into test cases; prioritize partition and clock-skew scenarios that violate user-visible guarantees.

Open questions

• How do you prevent “operator fixes” from changing safety properties?
• Where does your protocol assume synchrony without admitting it?
• Which invariants are violated first under overload: latency, availability, or correctness?
• What is the worst-case recovery time after a leader + disk failure?

Checklist

• Assumptions listed and reviewed.
• Telemetry captures correctness signals.
• Costs bounded (CPU/memory/bandwidth) under adversarial inputs.
• Failure modes enumerated with mitigations.
• Safety properties stated as invariants.
• Rollback plan rehearsed and automated.

Further reading

• Paxos Made Simple (Lamport) — Agreement basics and the invariants that matter.
• In Search of an Understandable Consensus Algorithm (Raft) — Consensus with explicit state machines and practical tradeoffs.
• Jepsen — Testing correctness under partitions and faults.
• Time, Clocks, and the Ordering of Events (Lamport) — Causality, ordering, and why clocks are tricky.
• Learn TLA+ — Practical entry point for specification and model checking.
• Site Reliability Engineering (Google) — Error budgets, incident response, and reliability as an engineering discipline.