Replication

State-machine replication means that replicas begin from equivalent state and apply the same ordered sequence of deterministic commands. If the transition function is deterministic and all replicas observe the same initial state and log order, they should produce equivalent results. The hard part is agreeing on the command sequence under failures. A replicated log may be established using a consensus protocol, with a leader proposing entries and quorum rules determining which entries become committed. Replication without agreement is not enough: two replicas can have identical code but diverge when they execute conflicting commands in different orders. Commands should be expressed in stable application terms, for example 'reserve seat 27 for operation key K' rather than 'run arbitrary code now'. The latter may read local time, filesystem state, or randomness and produce different results on each replica.

Determinism is more subtle than avoiding an explicit random function. Hash-map iteration order, locale-dependent formatting, floating-point corner cases across runtimes, non-versioned external API calls, and race conditions can change outputs. A robust state-machine command supplies any required timestamp, unique sequence number, or randomness as agreed input. Some services deterministically evaluate a command and record its effect rather than replay arbitrary application execution. Each replica must also know which commands are committed and may safely be exposed to clients. Applying an uncommitted proposal as durable fact can force a painful rollback after a leader change. Snapshots reduce replay work by capturing a state together with an applied log index and appropriate integrity metadata. A snapshot without a matching log position is insufficient evidence of recovery correctness.

Consider a replicated student registration database. The log contains commands to add a course, set its capacity, and enroll specific operation identifiers. Each transition checks an invariant: enrollment count may not exceed the capacity. The order matters when two clients attempt to acquire the final seat. If every replica applies one common committed order, exactly one enrollment succeeds. If replicas independently accept local commands and merge counters later, they may both claim confirmation. The state machine can return the same result for duplicate operation identifiers by storing previous outcomes, allowing retries after ambiguous responses. Snapshotting that state must retain deduplication records for their specified retention horizon, or an old retry arriving after recovery may execute again. This combines application idempotency with log ordering, a relationship frequently overlooked in toy consensus demos.

State-machine replication has costs even when it works correctly. Coordinated writes incur network round trips and durable storage overhead, and a hot global log can become a throughput bottleneck. Partitioning independent keys into separate consensus groups reduces contention but complicates operations spanning groups. Applying commands may be CPU-intensive, creating follower lag despite healthy replication links. Leadership changes can leave uncommitted log suffixes that require reconciliation. A system's recovery story should specify how replicas restore from snapshots, verify checksums, identify the committed prefix, and reject unsafe commands after membership changes. It should also distinguish a correct mathematical replication model from an actual deployment that depends on file-system durability and hardware failure modes.

Create a three-replica log visualizer where the learner appends two proposed commands, acknowledges them at selected voters, and advances the committed index only according to a defined quorum rule. Keep 'appended', 'committed', and 'applied' states separate and visible. Let a leader crash with an uncommitted suffix, elect a different leader, and inspect how commands from the old suffix may be replaced while the committed prefix must remain. Use a deterministic transition function for a small inventory map; compare state hashes only after the same committed prefix has been applied. Demonstrate a deliberately nondeterministic command that calls each replica's local random generator, and show divergent state hashes despite identical log entries. The animation is a bounded teaching model, not a complete Raft implementation.

Primary–backup replication assigns an active primary to handle designated updates while backups receive records or state copies. In synchronous variants the primary may wait for backups before returning a confirmed success; in asynchronous variants it may acknowledge earlier, accepting a window of possible lost updates. The choice affects recovery-point objectives and latency. Calling a backup 'hot' or 'ready' says little unless the system specifies which writes it has durably received and applied. A failover protocol must prevent the old primary from continuing authoritative updates after another primary takes over. Epochs or terms provide a fencing mechanism, and a reliable authority or quorum must decide whose writes are valid. Merely switching a load balancer DNS target does not provide write fencing.

Suppose a small merchant database performs 100 updates per second. It acknowledges each write immediately after local durable append and ships changes to its backup with average delay 200 milliseconds. Under stable load, the expected number of acknowledged updates not yet at the backup is approximately 100×0.2=20, although real queueing and burstiness change the distribution. If the primary is destroyed with no surviving copy of those updates, the service may lose acknowledged data. The calculation is an illustrative mean backlog under simple steady-state assumptions, not a guarantee about a particular failure. A synchronous secondary acknowledgement can narrow that window but increases latency and may reduce availability when the secondary is unreachable. The product should choose the rule deliberately and disclose which acknowledgement means 'durable against one node loss'.

Failover testing must examine old-primary recovery. Imagine primary P loses its route to the control plane while clients can still reach it. Backup B is promoted and accepts new writes. When the route is repaired, P reconnects with a divergent log. If it blindly republishes its writes, B may be overwritten or duplicates may leak to downstream consumers. Safe recovery treats P as a follower or repair source under a new authority epoch; it reconciles the accepted history according to the system's actual commit semantics. In a simplified single-primary database without a consensus group, automatic failover may be impossible to make safe under every partition pattern; operators may need a manual fencing step to avoid dual primaries. These limitations should be in the incident playbook before an outage occurs.

Backup design is not just a question of number of copies. Restore time, point-in-time recovery, immutable backups, schema compatibility, encryption-key availability, and disaster recovery drills determine whether a surviving copy is useful. A replica that continuously follows the primary may eagerly reproduce accidental deletions or corrupted data. Backups with retention and versioning protect against a different class of failure than real-time failover. It is useful to describe recovery time objective as a target for restoring service and recovery point objective as a target for acceptable data loss. Neither target is an observed guarantee without drills and measurements. A resilient strategy may combine synchronous in-region replicas, asynchronous cross-region copies, and periodic immutable backups, with different roles in the failure model.

Implement a primary–backup simulator with controls for write arrival rate, replication delay, acknowledgement strategy, crash instant, and promotion epoch. Plot the sequence of locally durable, copied, and client-acknowledged writes. When running asynchronously, count updates that were acknowledged but absent from the surviving backup at crash time. For the synchronous setting, mark requests awaiting replication and show their extra response delay. Then reconnect the old primary and test that it cannot write with a stale epoch. Ask learners to state precisely what their simulation does not represent: torn disk writes, Byzantine backup behavior, external downstream effects, and backups stored in another administrative domain. A correct result is a trace accompanied by explicit assumptions, not a smooth animation.

Quorum replication uses overlapping sets of participants to constrain which operations can proceed. In a simple majority voting group with N members, any two majorities intersect in at least one member because each has more than half the voters. That intersection supports safety arguments for consensus protocols when combined with the full rules on terms, durable promises, and log positions. In a leaderless replicated key-value store, engineers may choose read count R and write count W over replication factor N, often using the heuristic R+W>N for overlap. This overlap alone does not guarantee linearizable reads: concurrent writes, sloppy quorums, hinted handoff, stale acknowledgements, and lack of read repair can defeat stronger assumptions. State which quorum model is being analyzed rather than treating one arithmetic inequality as an entire consistency proof.

For N=5, R=3, W=3, read and write sets must intersect because 3+3>5. However, the common member might return a stale version when writes are still propagating or when the protocol permits different failure semantics. A read coordinator needs a version-selection and perhaps reconciliation procedure. With N=5, R=1, W=5, reads are cheap and writes require all replicas; one offline member can prevent progress under a strict interpretation. With R=5, W=1, write availability is higher but reads are fragile. These choices move latency and availability costs between operations. They are not optimal independently of read/write traffic, network geography, conflict rate, and recovery process. Also distinguish an intended replica set from the nodes that temporarily accept hints for unavailable replicas.

Imagine a distributed ticketing service holding five replicas of the remaining inventory count. It chooses R=3 and W=3 and lets two clients concurrently decrement separate copies. Even though each write reaches three nodes, the application can oversell if it performs read-modify-write without comparing versions or applying a serialized transaction. Each client could read one remaining ticket and write zero using a different causal history. Quorum overlap helps discover or constrain versions, but does not make a non-atomic multi-step business operation safe. Implement conditional writes or route the inventory invariant through an authoritative state machine. For other workloads, such as a comment 'like' count, a mergeable increment operation may eliminate the need for serializing every event. Consistency requirements should be derived from user-visible invariants, not merely chosen by a replica count formula.

Membership and repairs complicate quorum reasoning. A store may use virtual nodes and consistent hashing to decide owners; changing ownership during scaling affects which sets a quorum intersects. A client should not quietly believe that a request succeeded merely because three random nodes responded if the current configuration defines a different eligible set. Replicas that were offline need anti-entropy or log catch-up before serving authoritative reads. In leader-based consensus, a voting majority cannot be replaced by a collection of read-only observers. Under split-brain incidents, the operator should inspect configuration epochs, voter identities, write acknowledgements, and whether the safety invariant actually held, rather than relying on green host-health indicators.

Build a quorum grid for N from 3 to 9. Learners choose R and W and click replica nodes to represent read and write participants. Highlight the guaranteed intersection when R+W>N, but label the result 'set intersection only'. Provide a second mode for majority-of-N voting and enumerate candidate majority subsets to show that any two must intersect. Construct an example in which a shared node acknowledges a value before it is durably stored; then let that node crash and observe why durability assumptions matter. Ask students to modify a ticketing update to require a compare-and-swap condition and explain why the set-intersection calculation does not replace transaction logic. This intentionally separates mathematics of set intersection from implementation-level guarantees.

When replicas accept concurrent writes, the system must decide what those writes mean together. A conflict is not necessarily an error; it is evidence that no single observed ordering determines the result. Last-write-wins registers pick one value according to a chosen total order, often a timestamp with a tie-breaker. This is simple but can lose one user's intentional update, and unsynchronized clocks make 'latest' ambiguous. Multi-value registers retain concurrent alternatives for application resolution. Version vectors can detect that two values are concurrent rather than one overwriting the other. Conflict-free replicated data types, or CRDTs, instead define state or operation merges with algebraic properties that guarantee convergence under specified delivery assumptions. Convergence is not equivalent to every possible application invariant being preserved.

An observed-remove set is more nuanced than a naive set union. A user adds tag 'reviewed' and another user concurrently removes the tag. Whether the final state includes it depends on the chosen add-wins or remove-wins semantics. In an observed-remove design, removal typically targets additions the remover has observed; concurrent unseen additions may survive. This may suit collaborative annotation but not revoking critical access rights. A counter CRDT can merge independent positive increments without losing them by tracking per-replica contributions or equivalent causal metadata. A bounded inventory counter is different: unconstrained local increments and decrements can violate a non-negative invariant during partition. Escrow techniques allocate rights to decrement, limiting local operations without a global round trip. These approaches work because the invariant and transfer rights are designed together.

Consider a shared campus reading list. Alice offline adds a reference to Paper X, while Bob offline adds Paper Y. A grow-only set merged by union retains both, a desirable result. Later Alice removes Paper X while Bob—unaware of the removal—edits its annotation. What should happen? The data structure cannot make the educational product decision for you. One application may hide the reference but preserve annotation history; another may restore the item with a conflict marker; another may require explicit moderation. The merge structure should represent intentions with unique operation IDs and causal context, not merely replace an entire JSON document with the version whose server clock is greatest. A useful test makes both operation orders and a partitioned execution produce the documented semantic outcome.

CRDT descriptions should specify convergence assumptions. State-based CRDT merges are often designed to be associative, commutative, and idempotent, so merging duplicate or reordered states yields the same result. Operation-based variants may rely on dependable causal delivery or equivalent metadata. Tombstones and causal context can grow and require carefully designed garbage collection; premature cleanup may let deleted items reappear when a long-offline replica returns. Security is not automatically handled: a mathematically convergent structure can faithfully merge malicious unauthorized edits. Authorization and trusted identity remain external requirements. For a single-seat reservation, strict serializability or escrow rights may be simpler than trying to invent a conflict resolution rule after accepting contradictory confirmations.

Implement two-replica experiments for a last-write-wins register, multi-value register, and grow-only set. Let the learner send two concurrent updates while disconnected, then deliver them in either order. Show how set union converges and how last-write-wins discards one value. Repeat with a forged clock 24 hours ahead, illustrating the risk of wall-clock winners. In a second task, use per-replica G-counter components and merge by componentwise maximum; verify that counts converge after duplicate and reordered state transmissions. Add an intentionally invalid bounded decrement to show how mathematical convergence can coexist with an unacceptable negative inventory. The conclusion should be a statement of product invariants and merge semantics rather than an assertion that one data type fits every domain.

A laboratory equipment inventory tracks physical devices, their custodians, calibration status, and reservations. A misplaced instrument has financial and safety consequences, so the inventory needs more than eventually matching replica byte strings. The first requirement is a stable identity for each device; the second is an explicit ownership invariant for operations that allocate exclusive equipment; the third is an audit trail of custody transfers. Some data fields, such as last-inspected notes, can be updated independently and reconciled. Others, such as 'currently assigned to exactly one researcher', need an authoritative transition. Model the system as a state machine with command identifiers and versioned state. Separate a tentative reservation from a confirmed assignment so a disconnected client never invents authority. This provides the domain definition needed to assess replication mechanisms.

Partition the inventory by laboratory or device group rather than by arbitrary server process. Each partition can have its own replication group, improving scale without requiring one global log. However a single device transfer from Lab A to Lab B may touch two partitions, creating a cross-shard invariant. One approach reserves the device in the source partition, records a transfer intent, and completes ownership change through a coordinated workflow. Another uses a transaction service offering the necessary isolation and atomicity, with higher coordination costs. Neither approach should be hidden behind a simple 'move device' button that always returns instant success. The UI may show transfer pending until the durable new owner is confirmed and the prior owner is invalidated.

A failure trace clarifies the distinction between replication and durable acknowledgement. Primary P records transfer T, but before the backup has durably received it P returns success and immediately crashes. Backup B is promoted and lacks T. If the business contract promised loss-free confirmed transfers under any single-node failure, this behavior violates it. A synchronous quorum-based commit could protect the operation, at the cost of waiting for additional persistence. A replica whose local log includes T but whose commit index does not may need to discard T during leader reconciliation. The incident analysis should compare acknowledged, durable, committed, and applied indices separately. A screenshot of equal file sizes is not proof that both replicas accepted the same history.

Conflict-free merge techniques have a place in the same product. Independent tags, comments, and sensor readings may be modeled with convergent data types. A calibration counter that only increases can merge monotonic contributions from different facilities, but a claim that one expensive spectrometer can be checked out in two locations at once cannot be repaired by simply merging counters. If the device allocation policy requires uniqueness, use constrained rights, leases with fencing, or a strongly consistent owner. A background anti-entropy process can reconcile non-critical annotations; it should not overwrite confirmed custody records based solely on wall-clock freshness. Distinguish the guarantees of each field and publish them in the application contract.

Finally design a restore drill. Take a snapshot at log index S, then record new committed events through C>S. Destroy one replica and restore from the snapshot plus committed suffix. Verify the resulting state hash, every operation key's prior result, and the audit chain for custody transfers. Then repeat with a corrupt log block and require restoration to halt rather than silently skip it. A snapshot copied into three locations is not useful if all copies are encrypted with a lost key, so the drill needs a tested key-recovery policy. Record the elapsed restore time and the recovered committed index to compare with targets. This capstone integrates replication correctness, conflict resolution, backup design, and truthful operations reporting.