Distributed consensus, replication, and fault tolerance / personal lessonsLesson 15 of 17
Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Consensus is not a distributed transactionNext: When replicas can lie
Distributed systems · Lesson 15

Leaderless replication and conflict-free data

Understand version conflicts, repair, and the limits of merging.

By the end: Decide whether a data type can safely merge concurrent updates without a shared decision.

Availability can move conflict resolution to another stage

A leaderless or multi-writer design may accept writes through several replicas instead of routing every update through one current leader. During a partition this can preserve local write availability, but concurrent versions may disagree. Detecting and resolving those versions is part of the data model, not a housekeeping detail to postpone indefinitely.

Dynamo describes vector-based versioning, application-assisted reconciliation, and techniques such as hinted handoff and anti-entropy. Hinted handoff temporarily stores data intended for an unavailable replica and forwards it later. Anti-entropy compares replica state and repairs differences; Merkle trees summarize regions so a mismatch can be narrowed without sending every record. These mechanisms depend on eventual communication and correct repair. Sloppy quorums can use reachable substitute nodes, so fixed-set intersection arithmetic must not be applied without checking actual placement.

Repair transports versions but does not choose their meaning

A multi-writer store must answer two separate questions after replicas reconnect. Which updates are missing, and what state should those updates produce together? Repair addresses the first question by exchanging versions or summaries. Reconciliation addresses the second through application or data-type rules. Copying every byte between replicas can reveal a conflict without deciding it. For example, learning that Ada and Bo both edited a delivery address does not explain whether either edit supersedes the other, whether fields can be combined, or whether a person must choose a valid address.

Use a separate version-history case. A and B begin with address version V. A receives a change of street while isolated from B. B receives a change of city while isolated from A. Each update descends from V, but neither observed the other update. Under suitable version metadata they are concurrent. The word concurrent describes this missing dependency, not proof that both customers clicked at the same physical instant. Even if one click occurred later on a synchronized clock, it need not have been a correction of the earlier change because the later writer had never seen it.

A merge that combines the street and city might create an address nobody intended. Keeping both versions avoids silently discarding information, but leaves the application with unresolved work. Picking the version with the largest timestamp makes a deterministic choice if ties are handled consistently, but that choice may discard an independent update. These policies can all be implementable. Their correctness depends on the specified meaning of an address update. Causal metadata describes dependencies and concurrency. It does not contain the business rule needed to choose among these outcomes.

Repair must eventually propagate the information a merge rule needs. Suppose a temporary substitute stores B's update during an outage. Hinted handoff can later send it to the intended replica, but the transfer does not decide whether that update conflicts with A's. If the substitute becomes permanently unreachable before any other durable copy receives the update, eventual communication among the remaining replicas cannot recreate the missing information. State the retention, durability, and eventual-delivery assumptions rather than treating repair as a guarantee that any accepted update is recoverable under arbitrary failures.

Anti-entropy summaries have a narrower role. Imagine each replica hashes several key ranges and compares corresponding summaries. Unequal summaries identify a region that needs closer comparison. Sending the records or versions for that region can discover the actual mismatch. Equality of the summary is useful only under the hash and comparison assumptions; a summary is not a semantic proof that all stored addresses are valid. The lesson's counter experiment does not implement hashes, substitute placement, version pruning, or a general conflict-resolution service. Those mechanisms explain why receiving missing state and interpreting concurrent updates remain different tasks.

Convergence and correctness are different claims

Last-write-wins chooses one version using an ordered timestamp or tag, with a tiebreaker. This can make replicas converge while discarding a real concurrent update. A skewed wall clock can make an older real-world action win. Even perfectly synchronized timestamps would not explain whether merging two seat owners is acceptable. The ordering rule must match the application’s intended meaning.

A conflict-free replicated data type, or CRDT, uses update and merge rules designed to converge under specified delivery assumptions. For a state-based grow-only counter, keep a separate nondecreasing count for each actor. An actor increments its own component. Merge by componentwise maximum and report the sum. Maximum is associative, commutative, and idempotent, so delivery order and repeated delivery do not change the eventual merged state when all updates propagate.

Derive maximum merging from cumulative local evidence

A grow-only counter has a more restricted meaning than an editable address. Each actor reports how many increments it has originated so far. For two fixed actors, write the state as two components ordered A then B. Only A originates increments recorded in the first component, and only B originates increments recorded in the second. Either replica can learn a larger component through merge. Each component is a cumulative count, not a batch waiting to be added at every delivery. This interpretation makes a larger A component include the increments represented by a smaller A component.

Take a separate paper case in which A has originated three increments and B has originated two. A's local state might be [3,0] because it has not heard from B. B's local state might be [1,2] because it previously learned only A's first increment. The first components do not represent independent groups of three and one increments. The one is already included in the three. Taking the maximum therefore preserves A's three known increments without counting its first increment twice. Taking the maximum of the second components preserves B's two. The merged result is [3,2], whose reported total is five.

Why does message order not matter? For one component, the largest number among several received counts is independent of the order in which those numbers arrive. Grouping deliveries also leaves the largest number unchanged. Receiving the same count again does not create a larger maximum. These are the componentwise reasons behind commutativity, associativity, and idempotence. The properties describe merge, not arbitrary application commands. An increment still changes the owning actor's component, and losing an increment before it becomes durable or replicated is a separate storage failure outside the experiment's assumptions.

The construction can be described by an ordering on states. State X is no newer than state Y when every component of X is at most the corresponding component of Y. Merge returns the smallest state that is at least both inputs in this ordering. With [3,0] and [1,2], any such state needs an A component of at least three and a B component of at least two. The componentwise maximum supplies exactly those bounds. No choice of arrival order is needed because the states have a defined way to preserve the information represented by both.

Convergence still needs propagation. If updates stop and every replica eventually receives enough state to learn the largest component for every actor, all compute the same vector and total. An isolated replica can remain behind for an unbounded interval. Idempotent merging does not impose a delivery deadline or prove that a read is linearizable. A read during isolation can return a smaller total even after another replica has acknowledged an increment. The data type trades the need for a common order of these increments for a contract that permits such temporary disagreement.

Work through the model

Increment separately, then exchange state

Two fixed actors, A and B. Each owns one counter component. Buttons represent independent local updates and whole-state deliveries; there are no resets of actor identity or storage failures in this model.

Replica A

Vector [0, 0]

Total 0

Replica B

Vector [0, 0]

Total 0

Increment once at each replica, then deliver in both directions. Both totals become 2. Repeated delivery does not increase them. Reset starts a new experiment, not a safe in-service actor reset.
Counter stateA componentB componentReported total
A after own increment101
B after own increment011
Merge by maxima112
Receive the same merge again112
This is a two-actor state-based grow-only counter. Duplicate state delivery does not duplicate increments.

Read each delivery as a cumulative state merge

The experiment exposes two local increment buttons and two directional delivery buttons. Each delivery takes the other replica's current whole vector and merges it into the receiving replica. It is not a queued network packet with a separately selectable send time. Therefore, to observe a receiver behind its peer, leave one delivery direction unused while continuing local increments. The fixed table below the controls summarizes one increment at each actor and duplicate delivery. Neither the table nor the buttons elect a leader, validate a database, or add changing membership to the counter.

A guided sequence develops the ownership rule without introducing new controls. Start a fresh experiment. Increment at A twice and at B once. Before exchanging state, A should report [2,0] with total two, while B reports [0,1] with total one. Deliver A to B. B now has [2,1] and reports three, while A still reports two. The differing totals do not show a merge error. Only B has learned both contributions. Deliver B to A and both states become [2,1]. Repeating either delivery leaves the components unchanged.

Continue that same experiment by incrementing at A once more. A becomes [3,1], while B remains [2,1] until it receives another delivery. Deliver B to A before sending A to B. A must remain [3,1] because receiving a smaller A component cannot reduce its own count. This explains how the same merge rule handles a receiver that already knows more. Finally deliver A to B. Both reach [3,1]. The total of four comes from three distinct increments originated at A and one originated at B, not from the number of deliveries performed.

Stable actor identity is essential to that interpretation. For a separate failure case, suppose A once reached component five and B learned it. A loses its durable state, restarts under the same actor identity at zero, and performs two new increments. B merges that reported component two with its remembered five and keeps five. The two new events disappear from the total because the metadata falsely presents them as part of the same cumulative sequence. This failure cannot occur through the controls, which model no storage loss and no reuse of an actor after losing its count.

Assigning a fresh identity after replacement can distinguish the new increments, but introduces a membership and metadata-retention problem that the fixed two-component model avoids. Every replica must interpret actor components consistently, and old contributions must not vanish when an identity retires. Simply deleting an old component reduces the total and loses evidence needed for future merges. Reset counter experiment deliberately starts a separate demonstration with empty state. It is not a command a live service can use to reset one actor safely while retaining the previous experiment's promises and pending messages.

Derive the restriction from the invariant

If A independently increments from [0,0] to [1,0] and B to [0,1], their merged state is [1,1] and the total is 2. Adding whole states instead would count repeated deliveries twice. Component ownership and stable identity matter: reusing an actor identity after forgetting its count can break the model. Other data types need other constructions; a grow-only counter does not support arbitrary decrements or a hard maximum by itself.

For a unique seat, two sides can each locally satisfy “empty before reservation” and jointly violate “at most one owner.” No merge rule can make both already-promised exclusive reservations true. You must coordinate before promising exclusivity, preallocate disjoint rights such as inventory quotas with a proven bound, or weaken the business contract. A system can converge after retracting one promise, but that is not preservation of the original safety guarantee.

Test the invariant against independent local success

To decide whether coordination is needed, start with independently allowed updates and examine their combined result. A grow-only count with no upper bound accepts independent increments because retaining all contributions satisfies its intended meaning. Add the rule that the total must never exceed ten, and the same update mechanism no longer suffices. The merge can still converge perfectly while producing eleven. The property missing from the merge is not agreement about the arithmetic. It is an authorization rule preventing independently accepted work from exceeding the shared limit.

Consider a separate quota case with eight units already used and two units remaining. A and B each know this state, then become disconnected. A accepts two more uses because its local total reaches ten. B independently accepts one because its local total reaches nine. Combining the accepted contributions produces eleven. Every local check passed against the information available there. Later selecting a smaller total would hide an accepted use rather than preserve the hard bound. Refunding or rejecting an earlier success would change the contract, just as retracting an exclusive reservation changes what success originally meant.

Preallocated rights can change this example. Assign A one of the two remaining rights and B the other before disconnection. Each accepts at most one additional use without consulting the other. Their combined new usage cannot exceed two because the rights are disjoint and conserved. A cannot accept a second use merely because B's right appears idle. Transferring a right requires a protocol that prevents both sides from spending it during uncertainty. This is a conceptual allocation case, not an extra counter-widget capability or a claim that componentwise maximum alone implements a bounded inventory system.

Deletion reveals another limit of grow-only information. Suppose a set-like application removes an item by simply forgetting it, while an isolated replica still retains an older copy. When repair later exchanges state, the application must distinguish an old surviving copy from a genuinely new addition. Keeping a durable deletion marker can preserve that distinction, but reclaiming the marker requires evidence or assumptions about old replicas and delayed information. Other CRDT constructions specify their own deletion semantics and metadata. The grow-only counter proves no general theorem that arbitrary additions, removals, and invariants can use its same merge rule.

The design question is therefore which facts can be combined without invalidating completed promises. If temporary disagreement is permitted and all contributions have compatible meaning, a suitable merge can avoid ordering every update globally. If a request promises exclusive ownership or consumes a scarce right, identify where authorization is coordinated or how disjoint rights were allocated. Authentication can identify the actor that supplied a component, but cannot make a dishonest actor obey its increment rule. The experiment assumes correct actors and stable ownership. The next lesson changes that failure model and examines why an authenticated sender is not necessarily an honest participant.

Exercises

Why not add counter states?

A sends its full state [3,0] twice to B. What goes wrong if B adds incoming components instead of taking maxima?

Hint

The message is a state snapshot, not proof of a new increment.

Worked answer
Merge ruleAfter first [3,0]After duplicate [3,0]
Componentwise max from [0,0][3,0][3,0]
Componentwise sum from [0,0][3,0][6,0], incorrect
A repeated state must not become a new business event.

B can count A’s same three increments twice. Componentwise maximum retains 3 on repeat delivery. Operation-based counters have different requirements, such as handling duplicate operations; do not mix their delivery rules with this state-based construction.

Can a seat register be merged like a cart?

Two isolated replicas each promise exclusive seat 12 to a different buyer. Can a later merge preserve both successful exclusive reservations?

Hint

Consider the invariant, not whether the data structures can be combined.

Worked answer
Merged resultConsequence
Ada and Bo both own seatExclusivity violated
Only Ada owns seatBo’s prior promise retracted
Only Bo owns seatAda’s prior promise retracted
A merge policy cannot satisfy incompatible completed promises.

No. Keeping both owners violates exclusivity; removing either breaks an already-promised reservation. Coordinate the decision, allocate non-overlapping ownership rights in advance, or explicitly offer tentative reservations with possible rejection. Eventual convergence does not repair an impossible promise.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.

Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Consensus is not a distributed transactionNext: When replicas can lie